Content deleted Content added
m →Transformation between variants of finite automata: General fixes, removed erroneous space |
Citation bot (talk | contribs) Alter: template type. Add: s2cid. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 249/563 |
||
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]]<ref name="Birget1993a">{{cite journal|last1=Birget|first1=Jean-Camille|title=State-complexity of finite-state devices, state compressibility and incompressibility|journal=Mathematical Systems Theory|volume=26|issue=3|year=1993|pages=237–269|issn=0025-5661|doi=10.1007/BF01371727|s2cid=20375279}}</ref> used more states.
* 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}}</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>
Line 100:
| pages = 421–447
| doi = 10.1007/s00224-013-9465-0
| s2cid = 14808151
}}</ref>
Line 187 ⟶ 188:
===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 255 ⟶ 256:
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
| |||