Revision as of 08:39, 1 June 2019 edit A3nm (talk \| contribs) Extended confirmed users, Pending changes reviewers 4,578 edits mention exponential lower bound Tag: 2017 wikitext editor ← Previous edit		Revision as of 08:44, 1 June 2019 edit undo A3nm (talk \| contribs) Extended confirmed users, Pending changes reviewers 4,578 edits →Computational complexity: explain what "inevitable" means Tag: 2017 wikitext editor Next edit →
Line 297: == Computational complexity == The regular expression constructed by the algorithm may have size at least exponential in the input DFA. This exponential blowup is inevitable, because there exist families of DFAs for which any equivalent regular expression must be of exponential size.<ref>{{Cite journal\|last=Gruber\|first=Hermann\|last2=Holzer\|first2=Markus\|date=2008\|editor-last=Aceto\|editor-first=Luca\|editor2-last=Damgård\|editor2-first=Ivan\|editor3-last=Goldberg\|editor3-first=Leslie Ann\|editor4-last=Halldórsson\|editor4-first=Magnús M.\|editor5-last=Ingólfsdóttir\|editor5-first=Anna\|editor6-last=Walukiewicz\|editor6-first=Igor\|title=Finite Automata, Digraph Connectivity, and Regular Expression Size\|url=https://link.springer.com/chapter/10.1007/978-3-540-70583-3_4\|journal=Automata, Languages and Programming\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=39–50\|doi=10.1007/978-3-540-70583-3_4\|isbn=9783540705833}}. Theorem 16.</ref> ==See also==

Kleene's algorithm: Difference between revisions