Skip to main content
Theoretical Computer Science

Return to Answer

replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

By improving a known construction, Hsien-Chih Chang gives a familygives a family of $n$-state NFAs $A_n$ for which the shortest word witnessing non-universality has length $2^{(1/5-o(1))n}$, and even to $2^{(1/3-o(1))n}$. This improves upon the previously known bound of $2^{(1/75-o(1))n}$ given in by Ellul et al. (2005).

References: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)

By improving a known construction, Hsien-Chih Chang gives a family of $n$-state NFAs $A_n$ for which the shortest word witnessing non-universality has length $2^{(1/5-o(1))n}$, and even to $2^{(1/3-o(1))n}$. This improves upon the previously known bound of $2^{(1/75-o(1))n}$ given in by Ellul et al. (2005).

References: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)

By improving a known construction, Hsien-Chih Chang gives a family of $n$-state NFAs $A_n$ for which the shortest word witnessing non-universality has length $2^{(1/5-o(1))n}$, and even to $2^{(1/3-o(1))n}$. This improves upon the previously known bound of $2^{(1/75-o(1))n}$ given in by Ellul et al. (2005).

References: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)

Source Link
Hermann Gruber
Hermann Gruber
  • 6.8k
  • 15
  • 3

By improving a known construction, Hsien-Chih Chang gives a family of $n$-state NFAs $A_n$ for which the shortest word witnessing non-universality has length $2^{(1/5-o(1))n}$, and even to $2^{(1/3-o(1))n}$. This improves upon the previously known bound of $2^{(1/75-o(1))n}$ given in by Ellul et al. (2005).

References: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)