Content deleted Content added
Citation bot (talk | contribs) m Alter: title, template type, issue. Add: isbn, series, format, url, citeseerx, chapter. Formatted dashes. You can use this bot yourself. Report bugs here. | User-activated. |
m Moving Category:Finite automata to Category:Finite-state machines per Wikipedia:Categories for discussion/Speedy |
||
| (32 intermediate revisions by 13 users not shown) | |||
Line 35:
The following results are known.
* NFA to DFA: <math>2^n</math> states. This is the [[subset construction]] by [[Michael O. Rabin|Rabin]] and [[Dana Scott|Scott]],<ref name="RabinScott1959">{{cite journal|last1=Rabin|first1=M. O.|last2=Scott|first2=D.|title=Finite Automata and Their Decision Problems|journal=IBM Journal of Research and Development|volume=3|issue=2|year=1959|pages=114–125|issn=0018-8646|doi=10.1147/rd.32.0114}}</ref> proved optimal by [[Oleg Lupanov|Lupanov]].<ref>{{cite journal
| last = Lupanov
| first = Oleg B.
Line 48:
* NFA to UFA: <math>2^n-1</math> states, see Leung.<ref name="Leung2005" /> There was an earlier smaller lower bound by Schmidt.<ref name="Schmidt1978" />
* SVFA to DFA: <math>\Theta(3^{n/3})</math> states, see Jirásková and [[Giovanni Pighizzini|Pighizzini]]<ref name="JiráskováPighizzini2011">{{cite journal|last1=Jirásková|first1=Galina|last2=Pighizzini|first2=Giovanni|title=Optimal simulation of self-verifying automata by deterministic automata|journal=Information and Computation|volume=209|issue=3|year=2011|pages=528–535|issn=0890-5401|doi=10.1016/j.ic.2010.11.017}}</ref>
* 2DFA to DFA: <math>n(n^n-(n-1)^n)</math> states, see [[Christos Kapoutsis|Kapoutsis]].<ref name="Kapoutsis2005">{{Cite book|last1=Kapoutsis|first1=Christos|title=Mathematical Foundations of Computer Science 2005|series=Lecture Notes in Computer Science|volume=3618|year=2005|pages=544–555|issn=0302-9743|doi=10.1007/11549345_47|isbn=978-3-540-28702-5|chapter=Removing Bidirectionality from Nondeterministic Finite Automata}}</ref> Earlier construction by [[John Cedric Shepherdson|Shepherdson]]<ref name="Shepherdson1959">{{cite journal|last1=Shepherdson|first1=J. C.|title=The Reduction of Two-Way Automata to One-Way Automata|journal=IBM Journal of Research and Development|volume=3|issue=2|year=1959|pages=198–200|issn=0018-8646|doi=10.1147/rd.32.0198}}</ref> used more states, and an earlier lower bound by Moore<ref name="Moore1971">{{cite journal|last1=Moore|first1=F.R.|title=On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata|journal=IEEE Transactions on Computers|volume=C-20|issue=10|year=1971|pages=1211–1214|issn=0018-9340|doi=10.1109/T-C.1971.223108|s2cid=206618275}}</ref> was smaller.
* 2DFA to NFA: <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>, see Kapoutsis.<ref name="Kapoutsis2005" /> Earlier construction by [[Jean-Camille Birget|Birget]]
* 2NFA to NFA: <math>\binom{2n}{n+1}</math>, see Kapoutsis.<ref name="Kapoutsis2005" />
** 2NFA to NFA accepting the complement: <math>O(4^n)</math> states, see [[Moshe Vardi|Vardi]].<ref name="Vardi1989">{{cite journal|last1=Vardi|first1=Moshe Y.|title=A note on the reduction of two-way automata to one-way automata|journal=Information Processing Letters|volume=30|issue=5|year=1989|pages=261–264|issn=0020-0190|doi=10.1016/0020-0190(89)90205-6|citeseerx=10.1.1.60.464}}</ref>
* AFA to DFA: <math>2^{2^n}</math> states, see [[Ashok K. Chandra|Chandra]], [[Dexter Kozen|Kozen]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=0004-5411|doi=10.1145/322234.322243|s2cid=238863413|doi-access=free}}</ref>
* AFA to NFA: <math>2^n</math> states, see Fellah, Jürgensen and Yu.<ref name="FellahJürgensen1990">{{cite journal|last1=Fellah|first1=A.|last2=Jürgensen|first2=H.|last3=Yu|first3=S.|title=Constructions for alternating finite automata∗|journal=International Journal of Computer Mathematics|volume=35|issue=1–4|year=1990|pages=117–132|issn=0020-7160|doi=10.1080/00207169008803893}}</ref>
* 2AFA to DFA: <math>2^{n2^n}</math>, see [[Richard E. Ladner|Ladner]], [[Richard J. Lipton|Lipton]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref>
* 2AFA to NFA: <math>2^{\Theta(n \log n)}</math>, see [[Viliam Geffert|Geffert]] and
===The 2DFA vs. 2NFA problem and logarithmic space===
Line 65:
there exists a <math>p(n)</math>-state 2DFA.
The problem was raised by Sakoda and [[Michael Sipser|Sipser]],<ref>{{cite conference
|
| first1 = William J.
| last1 = Sakoda
| first2 = Michael
| last2 = Sipser
| title = Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78
| year = 1978
| conference = STOC 1978
Line 76 ⟶ 77:
| pages = 275–286
| doi = 10.1145/800133.804357
| doi-access = free
}}</ref>
who compared it to the [[P vs. NP]] problem
Line 100 ⟶ 102:
| pages = 421–447
| doi = 10.1007/s00224-013-9465-0
| s2cid = 14808151
}}</ref>
Line 128 ⟶ 131:
<ref name="YuZhuang1994">{{cite journal|last1=Yu|first1=Sheng|last2=Zhuang|first2=Qingyu|last3=Salomaa|first3=Kai|title=The state complexities of some basic operations on regular languages|journal=Theoretical Computer Science|volume=125|issue=2|year=1994|pages=315–328|issn=0304-3975|doi=10.1016/0304-3975(92)00011-F}}</ref>
[[Markus Holzer|Holzer]] and [[Martin Kutrib|Kutrib]]
<ref name="HolzerKutrib2003">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=Nondeterministic descriptional complexity of regular languages|journal=International Journal of Foundations of Computer Science|volume=14|issue=6|year=2003|pages=1087–1102|issn=0129-0541|doi=10.1142/S0129054103002199|url=http://geb.uni-giessen.de/geb/volltexte/2003/1194/|
pioneered the state complexity of operations on NFA.
The known results for basic operations are listed below.
Line 136 ⟶ 139:
If language <math>L_1</math> requires m states
and language <math>L_2</math> requires n states,
how many states does <math>L_1 \cup L_2</math>
* DFA: <math>mn</math> states, see Maslov<ref name="Maslov" /> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>m+n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: at least <math>\min(n,m)^{\Omega(\log(\min(n,m)))}</math>;<ref name="GoosKieferYuan2022" /> between <math>mn+m+n</math> and <math>
* SVFA: <math>mn</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015">{{Cite book|last1=Jirásek|first1=Jozef Štefan|title=Computer Science -- Theory and Applications|last2=Jirásková|first2=Galina|last3=Szabari|first3=Alexander|volume=9139|year=2015|pages=231–261|issn=0302-9743|doi=10.1007/978-3-319-20297-6_16|series=Lecture Notes in Computer Science|isbn=978-3-319-20296-9}}</ref>
* 2DFA: between <math>m+n</math> and <math>4m+n+4</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012">{{cite journal|last1=Kunc|first1=Michal|last2=Okhotin|first2=Alexander|title=State complexity of operations on two-way finite automata over a unary alphabet|journal=Theoretical Computer Science|volume=449|year=2012|pages=106–118|issn=0304-3975|doi=10.1016/j.tcs.2012.04.010|doi-access=free}}</ref>
* 2NFA: <math>m+n</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011">{{cite journal|last1=Kunc|first1=Michal|last2=Okhotin|first2=Alexander|title=State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata |journal=Fundamenta Informaticae|volume=110|issue=1–4|year=2011|pages=231–239|doi=10.3233/FI-2011-540
===Intersection===
How many states does <math>L_1 \cap L_2</math>
* DFA: <math>mn</math> states, see Maslov<ref name="Maslov" /> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
Line 159 ⟶ 162:
If language L requires n states
then how many states does its ''[[complementation of automata|complement]]''
* DFA: <math>n</math> states, by exchanging accepting and rejecting states.
* NFA: <math>2^n</math> states, see Birget.<ref name="Birget1993b">{{cite journal|last1=Birget|first1=Jean-Camille|title=Partial orders on words, minimal elements of regular languages, and state complexity|journal=Theoretical Computer Science|volume=119|issue=2|year=1993|pages=267–291|issn=0304-3975|doi=10.1016/0304-3975(93)90160-U}}</ref> or Jirásková<ref>{{Cite journal |last=Jirásková |first=Galina |date=2005 |title=State complexity of some operations on binary regular languages |url=https://linkinghub.elsevier.com/retrieve/pii/S0304397504006577 |journal=Theoretical Computer Science |language=en |volume=330 |issue=2 |pages=287–298 |doi=10.1016/j.tcs.2004.04.011}}, Theorem 5</ref>
* UFA: at least <math>n^{\tilde{\Omega}(\log n)}</math> states, see Göös, Kiefer and Yuan,<ref name="GoosKieferYuan2022">{{cite arXiv |last1=Göös |first1=Mika |last2=Kiefer |first2=Stefan |last3=Yuan |first3=Weiqiang |title=Lower Bounds for Unambiguous Automata via Communication Complexity |date=12 February 2022 |class=cs.FL |eprint=2109.09155}}</ref> (this follows an earlier bound by Raskin<ref>{{Cite journal |last=Raskin |first=Mikhail |date=2018 |title=A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2018.138 |language=en |publisher=Schloss-Dagstuhl - Leibniz Zentrum für Informatik |doi=10.4230/LIPIcs.ICALP.2018.138|doi-access=free }}</ref>); and at most <math>\sqrt{n+1} \cdot 2^{0.5n}</math> states, see Indzhev and Kiefer.<ref>{{cite journal |last1=Indzhev |first1=Emil |last2=Kiefer |first2=Stefan |title=On complementing unambiguous automata and graphs with many cliques and cocliques |journal=Information Processing Letters |date=1 August 2022 |volume=177 |page=106270 |doi=10.1016/j.ipl.2022.106270 |s2cid=234741832 |url=https://ora.ox.ac.uk/objects/uuid:a36b96e8-fa8e-4ef9-b45b-2a625366cf54/files/rrj4305198 |access-date=29 May 2022 |ref=IndzhevKiefer22 |language=en |issn=0020-0190|doi-access=free |arxiv=2105.07470 }}</ref>
* SVFA: <math>n</math> states, by exchanging accepting and rejecting states.
* 2DFA: at least <math>n</math> and at most <math>4n</math> states, see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2007">{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Complementing two-way finite automata|journal=Information and Computation|volume=205|issue=8|year=2007|pages=1173–1187|issn=0890-5401|doi=10.1016/j.ic.2007.01.008|doi-access=free}}</ref>
===Concatenation===
How many states does <math>L_1 L_2 = \{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\}</math>
* DFA: <math>m \cdot 2^n - 2^{n-1}</math> states, see Maslov <ref name="Maslov" /> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
Line 187 ⟶ 190:
===Reversal===
* DFA: <math>2^n</math> states, see Mirkin,<ref name="Mirkin1966">{{cite journal|last1=Mirkin|first1=Boris G.|title=On dual automata|journal=Cybernetics|volume=2|year=1966|pages=6–9|doi=10.1007/bf01072247|s2cid=123186223}}</ref> Leiss,<ref name="Leiss1985">{{cite journal|last1=Leiss|first1=Ernst|title=Succinct representation of regular languages by boolean automata II|journal=Theoretical Computer Science|volume=38|year=1985|pages=133–136|issn=0304-3975|doi=10.1016/0304-3975(85)90215-4}}</ref> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: <math>n</math> states.
Line 205 ⟶ 208:
* NFA to DFA: <math>g(n)+O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />
* 2DFA to DFA: <math>g(n)+O(n)</math> states, see Chrobak<ref name="Chrobak1986" /> and Kunc and Okhotin.<ref name="KuncOkhotin2011b">{{Cite book|last1=Kunc|first1=Michal|title=Developments in Language Theory|last2=Okhotin|first2=Alexander|volume=6795|year=2011|pages=324–336|issn=0302-9743|doi=10.1007/978-3-642-22321-1_28|series=Lecture Notes in Computer Science|isbn=978-3-642-22320-4|citeseerx=10.1.1.616.8835}}</ref>
* 2NFA to DFA: <math>O(g(n))</math> states, see Mereghetti and [[Giovanni Pighizzini|Pighizzini]].<ref name="MereghettiPighizzini2001">{{cite journal|last1=Mereghetti|first1=Carlo|last2=Pighizzini|first2=Giovanni|title=Optimal Simulations between Unary Automata|journal=SIAM Journal on Computing|volume=30|issue=6|year=2001|pages=1976–1992|issn=0097-5397|doi=10.1137/S009753979935431X|hdl=2434/35121|hdl-access=free}}</ref> and [[Viliam Geffert|Geffert]], Mereghetti and Pighizzini.<ref name="GeffertMereghetti2003">{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Converting two-way nondeterministic unary automata into simpler automata|journal=Theoretical Computer Science|volume=295|issue=1–3|year=2003|pages=189–203|issn=0304-3975|doi=10.1016/S0304-3975(02)00403-6}}</ref>
* NFA to 2DFA: at most <math>O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />
* 2NFA to 2DFA: at most <math>n^{O(\log n)}</math> states, proved by implementing the method of [[Savitch's theorem]], see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2003" />
* UFA to DFA: <math>e^{\Theta(\sqrt[3]{n (\ln n)^2})}</math>, see Okhotin.<ref name="Okhotin2012">{{cite journal|last1=Okhotin|first1=Alexander|title=Unambiguous finite automata over a unary alphabet|journal=Information and Computation|volume=212|year=2012|pages=15–36|issn=0890-5401|doi=10.1016/j.ic.2012.01.003|doi-access=free}}</ref>
* NFA to UFA: <math>g(n)+O(n^2)</math>, see Okhotin.<ref name="Okhotin2012" />
Line 228 ⟶ 231:
* DFA: <math>n</math> states.
* NFA: <math>g(n)+O(n^2)</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: at least <math>n^{
* 2DFA: at least <math>n</math> and at most <math>2n+3</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: at least <math>n</math> and at most <math>O(n^8)</math> states. The upper bound is by implementing the method of the [[Immerman–Szelepcsényi theorem]], see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2007"/>
Line 255 ⟶ 258:
Surveys of state complexity
were written by Holzer and Kutrib<ref name="HolzerKutrib2009">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=Nondeterministic finite automata — recent results on the descriptional and computational complexity|journal=International Journal of Foundations of Computer Science|volume=20|issue=4|year=2009|pages=563–580|issn=0129-0541|doi=10.1142/S0129054109006747}}</ref><ref name="HolzerKutrib2011">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=Descriptional and computational complexity of finite automata—A survey|journal=Information and Computation|volume=209|issue=3|year=2011|pages=456–470|issn=0890-5401|doi=10.1016/j.ic.2010.11.013}}</ref>
and by Gao et al.<ref>{{cite
New research on state complexity
Line 267 ⟶ 270:
{{reflist}}
[[Category:Finite-state
| |||