Revisions to computing the minimal NFA for a DFA

broken link fixed, cf. https://math.meta.stackexchange.com/a/34713/228959

Source Link

edit approved Oct 4, 2022 at 9:45

359
1
4
10

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?

replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:48

Community Bot

1

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?What are the conditions for a NFA for its equivalent DFA to be maximal in size?

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?

grammar and language

Source Link

edit approved May 13, 2012 at 18:12

Juho

3.2k
2
27
36

many yrsMany years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question [as, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm]algorithm. hasHas anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem [apparently. Apparently, no algorithm(s) given] is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

fyiI was reminded of this problem by the following Qquestion on the new CS stackexchange.SE site for which a DFA->NFA minimization algorithm would be closely related. thisThis following question seems to me to be research level [suggest. I suggested migrating it to TCS] &TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?

many yrs ago heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question [as opposed to vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm]. has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem [apparently no algorithm(s) given].

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

fyi was reminded of this problem by the following Q on the new CS stackexchange site for which a DFA->NFA minimization algorithm would be closely related. this following question seems to me to be research level [suggest migrating it to TCS] & wrote an answer suggesting a statistical/empirical attack

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?