@inproceedings{SakodaSipser1978,
  author    = {William J. Sakoda and Michael Sipser},
  title     = {Nondeterminism and the Size of Two Way Finite Automata},
  booktitle = {Proceedings of the Tenth Annual {ACM} Symposium on Theory of Computing},
  series    = {STOC '78},
  publisher = {Association for Computing Machinery},
  address   = {New York, NY, USA},
  year      = {1978},
  month     = may,
  pages     = {275--286},
  doi       = {10.1145/800133.804357},
  url       = {https://doi.org/10.1145/800133.804357}
}

@misc{AdeogunKapoutsis2026,
  author        = {Kehinde Adeogun and Christos Kapoutsis},
  title         = {A Quadratic Lower Bound for {2DFAs} against One-Way Liveness},
  year          = {2026},
  howpublished  = {arXiv:2602.24279v2 [cs.FL]},
  note          = {Version 2, revised 6 July 2026},
  archivePrefix = {arXiv},
  eprint        = {2602.24279},
  primaryClass  = {cs.FL},
  doi           = {10.48550/arXiv.2602.24279},
  url           = {https://arxiv.org/abs/2602.24279v2}
}

@article{Auinger2012,
  author  = {Karl Auinger},
  title   = {{Krohn--Rhodes} Complexity of {Brauer} Type Semigroups},
  journal = {Portugaliae Mathematica},
  volume  = {69},
  number  = {4},
  year    = {2012},
  pages   = {341--360},
  doi     = {10.4171/PM/1921},
  url     = {https://ems.press/journals/pm/articles/11777}
}

@misc{CompanionComplementation2026,
  author = {{OpenAI}},
  title = {{An exponential state lower bound for two-way nondeterministic complementation}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/An-exponential-state-lower-bound-for-two-way-nondeterministic-complementation-September-25-2026/paper.pdf}{OAI:An-exponential-state-lower-bound-for-two-way-nondeterministic-complementation-September-25-2026}},
  year = {2026}
}

@article{RabinScott1959,
  author = {Michael O. Rabin and Dana Scott},
  title = {Finite Automata and Their Decision Problems},
  journal = {IBM Journal of Research and Development},
  volume = {3},
  number = {2},
  pages = {114--125},
  year = {1959},
  doi = {10.1147/rd.32.0114}
}

@article{Shepherdson1959,
  author = {John C. Shepherdson},
  title = {The Reduction of Two-Way Automata to One-Way Automata},
  journal = {IBM Journal of Research and Development},
  volume = {3},
  number = {2},
  pages = {198--200},
  year = {1959},
  doi = {10.1147/rd.32.0198}
}

@article{Sipser1980,
  author = {Michael Sipser},
  title = {Lower Bounds on the Size of Sweeping Automata},
  journal = {Journal of Computer and System Sciences},
  volume = {21},
  number = {2},
  pages = {195--202},
  year = {1980},
  doi = {10.1016/0022-0000(80)90034-3}
}

@article{Kapoutsis2013,
  author = {Christos Kapoutsis},
  title = {Nondeterminism Is Essential in Small Two-Way Finite Automata with Few Reversals},
  journal = {Information and Computation},
  volume = {222},
  pages = {208--227},
  year = {2013},
  doi = {10.1016/j.ic.2012.11.001}
}

@misc{AdeogunKapoutsisLimitation2026,
  author = {Kehinde Adeogun and Christos A. Kapoutsis},
  title = {Unrestricted {2DFA} Simulation of {1NFAs}: A Quadratic Limitation to a New Lower Bound},
  year = {2026},
  howpublished = {arXiv:2609.13793v2 [cs.FL]},
  note = {Version 2, revised 15 September 2026},
  archivePrefix = {arXiv},
  eprint = {2609.13793},
  primaryClass = {cs.FL},
  url = {https://arxiv.org/abs/2609.13793v2}
}

@article{Chrobak1986Unary,
  author = {Marek Chrobak},
  title = {Finite Automata and Unary Languages},
  journal = {Theoretical Computer Science},
  volume = {47},
  pages = {149--158},
  year = {1986},
  doi = {10.1016/0304-3975(86)90142-8},
  note = {Erratum in Theoretical Computer Science 302 (2003), 497--498}
}

@article{Chrobak2003Errata,
  author = {Marek Chrobak},
  title = {Errata to: ``Finite Automata and Unary Languages''},
  journal = {Theoretical Computer Science},
  volume = {302},
  pages = {497--498},
  year = {2003},
  doi = {10.1016/S0304-3975(03)00136-1}
}

@incollection{Kapoutsis2018ShortLiveness,
  author = {Christos A. Kapoutsis},
  title = {Optimal {2DFA} Algorithms for One-Way Liveness on Two and Three Symbols},
  editor = {Hans-Joachim B{\"o}ckenhauer and Dennis Komm and Walter Unger},
  booktitle = {Adventures Between Lower Bounds and Higher Altitudes:
    Essays Dedicated to Juraj Hromkovi{\v c} on the Occasion of His 60th Birthday},
  series = {Lecture Notes in Computer Science},
  volume = {11011},
  pages = {33--48},
  publisher = {Springer},
  address = {Cham},
  year = {2018},
  doi = {10.1007/978-3-319-98355-4_3}
}

@article{Brauer1937,
  author = {Richard Brauer},
  title = {On Algebras Which are Connected with the Semisimple Continuous Groups},
  journal = {Annals of Mathematics},
  series = {Second Series},
  volume = {38},
  number = {4},
  pages = {857--872},
  year = {1937},
  doi = {10.2307/1968843}
}

@article{EastGray2017,
  author = {James East and Robert D. Gray},
  title = {Diagram Monoids and {Graham--Houghton} Graphs: Idempotents and Generating Sets of Ideals},
  journal = {Journal of Combinatorial Theory, Series A},
  volume = {146},
  pages = {63--128},
  year = {2017},
  doi = {10.1016/j.jcta.2016.09.001}
}

@incollection{Pin1997,
  author = {Jean-{\'E}ric Pin},
  title = {Syntactic Semigroups},
  editor = {Grzegorz Rozenberg and Arto Salomaa},
  booktitle = {Handbook of Formal Languages},
  volume = {1},
  publisher = {Springer},
  address = {Berlin--Heidelberg},
  pages = {679--746},
  year = {1997},
  doi = {10.1007/978-3-642-59136-5_10}
}

@article{SipserHalting1980,
  author = {Michael Sipser},
  title = {Halting Space-Bounded Computations},
  journal = {Theoretical Computer Science},
  volume = {10},
  number = {3},
  pages = {335--338},
  year = {1980},
  doi = {10.1016/0304-3975(80)90053-5}
}

@article{LangeMcKenzieTapp2000,
  author = {Klaus-J{\"o}rn Lange and Pierre McKenzie and Alain Tapp},
  title = {Reversible Space Equals Deterministic Space},
  journal = {Journal of Computer and System Sciences},
  volume = {60},
  number = {2},
  pages = {354--367},
  year = {2000},
  doi = {10.1006/jcss.1999.1672}
}