@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},
  pages = {275--286},
  publisher = {Association for Computing Machinery},
  year = {1978},
  doi = {10.1145/800133.804357},
  note = {\href{https://doi.org/10.1145/800133.804357}{doi:10.1145/800133.804357}},
  url = {https://doi.org/10.1145/800133.804357}
}

@article{GeffertMereghettiPighizzini2007,
  author = {Viliam Geffert and Carlo Mereghetti and Giovanni Pighizzini},
  title = {Complementing Two-Way Finite Automata},
  journal = {Information and Computation},
  volume = {205},
  number = {8},
  pages = {1173--1187},
  year = {2007},
  doi = {10.1016/j.ic.2007.01.008},
  note = {\href{https://doi.org/10.1016/j.ic.2007.01.008}{doi:10.1016/j.ic.2007.01.008}},
  url = {https://doi.org/10.1016/j.ic.2007.01.008}
}

@inproceedings{GeffertMereghettiPighizzini2005,
  author = {Viliam Geffert and Carlo Mereghetti and Giovanni Pighizzini},
  title = {Complementing Two-Way Finite Automata},
  booktitle = {Developments in Language Theory},
  editor = {Clelia De Felice and Antonio Restivo},
  series = {Lecture Notes in Computer Science},
  volume = {3572},
  pages = {260--271},
  publisher = {Springer},
  year = {2005},
  doi = {10.1007/11505877_23},
  note = {\href{https://doi.org/10.1007/11505877_23}{doi:10.1007/11505877\_23}}
}

@inproceedings{GuillonPrigionieroTaheri2026,
  author = {Bruno Guillon and Luca Prigioniero and Javad Taheri},
  title = {Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata},
  booktitle = {43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {364},
  pages = {48:1--48:18},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year = {2026},
  doi = {10.4230/LIPIcs.STACS.2026.48},
  note = {\href{https://doi.org/10.4230/LIPIcs.STACS.2026.48}{doi:10.4230/LIPIcs.STACS.2026.48}},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.48}
}

@misc{CompanionDeterminization2026,
  author = {{OpenAI}},
  title = {{An exponential two-way deterministic state lower bound for one-way liveness}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/An-exponential-two-way-deterministic-state-lower-bound-for-one-way-liveness-September-25-2026/main.pdf}{OAI:An-exponential-two-way-deterministic-state-lower-bound-for-one-way-liveness-September-25-2026}},
  year = {2026},
  note = {Theorem~1.1 and Section~3}
}

@article{Vardi1989,
  author = {Moshe Y. Vardi},
  title = {A note on the reduction of two-way automata to one-way automata},
  journal = {Information Processing Letters},
  volume = {30},
  number = {5},
  pages = {261--264},
  year = {1989},
  doi = {10.1016/0020-0190(89)90205-6},
  note = {\href{https://doi.org/10.1016/0020-0190(89)90205-6}{doi:10.1016/0020-0190(89)90205-6}}
}

@inproceedings{Kapoutsis2006,
  author = {Christos Kapoutsis},
  title = {Small Sweeping {2NFAs} Are Not Closed under Complement},
  booktitle = {Automata, Languages and Programming (ICALP 2006)},
  series = {Lecture Notes in Computer Science},
  volume = {4051},
  pages = {144--156},
  publisher = {Springer},
  year = {2006},
  doi = {10.1007/11786986_14},
  note = {\href{https://doi.org/10.1007/11786986_14}{doi:10.1007/11786986\_14}}
}

@article{MartinMazorchuk2013,
  author = {Paul Martin and Volodymyr Mazorchuk},
  title = {Partitioned binary relations},
  journal = {Mathematica Scandinavica},
  volume = {113},
  number = {1},
  pages = {30--52},
  year = {2013},
  doi = {10.7146/math.scand.a-15480},
  note = {\href{https://doi.org/10.7146/math.scand.a-15480}{doi:10.7146/math.scand.a-15480}}
}