References

  1. Marcin Balcerzak & Damian Niwinski (2010): Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal. Inf. Process. Lett. 110(10), pp. 396–398, doi:10.1016/j.ipl.2010.03.008.
  2. Piotr Berman (1980): A note on sweeping automata. In: J. W. de Bakker & Jan van Leeuwen: ICALP, Lecture Notes in Computer Science 85. Springer, pp. 91–97, doi:10.1007/3-540-10003-2_62.
  3. Piotr Berman & Andrei Lingas (1977): On the complexity of regular languages in terms of finite automata. Technical Report 304. Polish Academy of Sciences.
  4. Marek Chrobak (1986): Finite automata and unary languages. Theor. Comput. Sci. 47(3), pp. 149–158, doi:10.1016/0304-3975(86)90142-8. Errata: Chrobak2003497.
  5. Marek Chrobak (2003): Errata to: Finite automata and unary languages: [Theoret. Comput. Sci. 47 (1986) 149-158]. Theor. Comput. Sci. 302(1-3), pp. 497 – 498, doi:10.1016/S0304-3975(03)00136-1.
  6. Pawel Gawrychowski (2011): Chrobak normal form revisited, with applications. In: Béatrice Bouchou-Markhoff, Pascal Caron, Jean-Marc Champarnaud & Denis Maurel: CIAA, Lecture Notes in Computer Science 6807. Springer, pp. 142–153, doi:10.1007/978-3-642-22256-6_14.
  7. Viliam Geffert (2007): Magic numbers in the state hierarchy of finite automata. Inf. Comput. 205(11), pp. 1652–1670, doi:10.1016/j.ic.2007.07.001.
  8. Viliam Geffert, Bruno Guillon & Giovanni Pighizzini (2012): Two-way automata making choices only at the endmarkers. In: Adrian Horia Dediu & Carlos Martín-Vide: LATA, Lecture Notes in Computer Science 7183. Springer, pp. 264–276, doi:10.1007/978-3-642-28332-1_23. Available at http://arxiv.org/abs/1110.1263.
  9. Viliam Geffert, Carlo Mereghetti & Giovanni Pighizzini (2003): Converting two-way nondeterministic unary automata into simpler automata. Theor. Comput. Sci. 295, pp. 189–203, doi:10.1016/S0304-3975(02)00403-6.
  10. Viliam Geffert, Carlo Mereghetti & Giovanni Pighizzini (2007): Complementing two-way finite automata. Inf. Comput. 205(8), pp. 1173–1187, doi:10.1016/j.ic.2007.01.008.
  11. Viliam Geffert & Giovanni Pighizzini (2011): Two-way unary automata versus logarithmic space. Inf. Comput. 209(7), pp. 1016–1025, doi:10.1016/j.ic.2011.03.003.
  12. John E. Hopcroft & Jeffrey D. Ullman (1979): Introduction to Automata Theory, Languages and Computation. Addison-Wesley.
  13. Juraj Hromkovič & Georg Schnitger (2003): Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser's separation. In: Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow & Gerhard J. Woeginger: ICALP, Lecture Notes in Computer Science 2719. Springer, pp. 439–451, doi:10.1007/3-540-45061-0_36.
  14. Neil Immerman (1988): Nondeterministic space is closed under complementation. SIAM J. Comput. 17(5), pp. 935–938, doi:10.1137/0217058.
  15. Christos Kapoutsis & Giovanni Pighizzini (2012): Reversal hierarchies for small 2DFAs. In: MFCS 2012, Lecture Notes in Computer Science. Springer. To appear.
  16. Christos Kapoutsis & Giovanni Pighizzini (2012): Two-way automata characterizations of L/poly versus NL. In: Edward A. Hirsch, Juhani Karhumäki, Arto Lepistö & Michail Prilutskii: CSR, Lecture Notes in Computer Science 7353. Springer, pp. 217–228.
  17. Christos A. Kapoutsis (2005): Removing bidirectionality from nondeterministic finite automata. In: Joanna Jedrzejowicz & Andrzej Szepietowski: MFCS, Lecture Notes in Computer Science 3618. Springer, pp. 544–555, doi:10.1007/11549345_47.
  18. Christos A. Kapoutsis (2011): Nondeterminism is essential in small 2FAs with few reversals. In: Luca Aceto, Monika Henzinger & Jiri Sgall: ICALP (2), Lecture Notes in Computer Science 6756. Springer, pp. 198–209, doi:10.1007/978-3-642-22012-8_15.
  19. Christos A. Kapoutsis (2011): Two-way automata versus logarithmic space. In: Alexander S. Kulikov & Nikolay K. Vereshchagin: CSR, Lecture Notes in Computer Science 6651. Springer, pp. 359–372, doi:10.1007/978-3-642-20712-9_28.
  20. Christos A. Kapoutsis (2012): Minicomplexity. In: Martin Kutrib, Nelma Moreira & Rogério Reis: DCFS, Lecture Notes in Computer Science 7386. Springer, pp. 20–42, doi:10.1007/978-3-642-31623-4_2.
  21. Christos A. Kapoutsis, Richard Královic & Tobias Mömke (2012): Size complexity of rotating and sweeping automata. J. Comput. Syst. Sci. 78(2), pp. 537–558, doi:10.1016/j.jcss.2011.06.004.
  22. R.M. Karp & R.J. Lipton (1982): Turing machines that take advice. In: E. Engeler et al: Logic and Algorithmic. L'Enseignement Mathématique, Genève, pp. 191–209.
  23. Michal Kunc & Alexander Okhotin (2011): Describing periodicity in two-way deterministic finite automata using transformation semigroups. In: Giancarlo Mauri & Alberto Leporati: Developments in Language Theory, Lecture Notes in Computer Science 6795. Springer, pp. 324–336, doi:10.1007/978-3-642-22321-1_28.
  24. Martin Kutrib, Andreas Malcher & Giovanni Pighizzini (2012): Oblivious two-way finite automata: decidability and complexity. In: David Fernández-Baca: LATIN, Lecture Notes in Computer Science 7256. Springer, pp. 518–529, doi:10.1007/978-3-642-29344-3_44.
  25. O.B. Lupanov (1963): A comparison of two types of finite automata. Problemy Kibernet 9, pp. 321–326. (in Russian). German translation: Über den Vergleich zweier Typen endlicher Quellen, Probleme der Kybernetik 6, 329–335 (1966).
  26. Carlo Mereghetti (2008): Testing the descriptional power of small Turing machines on nonregular language acceptance. Int. J. Found. Comput. Sci. 19(4), pp. 827–843, doi:10.1142/S012905410800598X.
  27. Carlo Mereghetti & Giovanni Pighizzini (2001): Optimal simulations between unary automata. SIAM J. Comput. 30(6), pp. 1976–1992, doi:10.1137/S009753979935431X.
  28. A. R. Meyer & M. J. Fischer (1971): Economy of description by automata, grammars, and formal systems. In: SWAT '71: Proceedings of the 12th Annual Symposium on Switching and Automata Theory (swat 1971). IEEE Computer Society, Washington, DC, USA, pp. 188–191.
  29. Silvio Micali (1981): Two-way deterministic finite automata are exponentially more succinct than sweeping automata. Inf. Process. Lett. 12(2), pp. 103–105, doi:10.1016/0020-0190(81)90012-0.
  30. F.R. Moore (1971): On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. Computers, IEEE Transactions on C-20(10), pp. 1211 – 1214, doi:10.1109/T-C.1971.223108.
  31. M. O. Rabin & D. Scott (1959): Finite automata and their decision problems. IBM J. Res. Dev. 3(2), pp. 114–125, doi:10.1147/rd.32.0114.
  32. William J. Sakoda & Michael Sipser (1978): Nondeterminism and the size of two-way finite automata. In: Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman & Alfred V. Aho: STOC. ACM, pp. 275–286, doi:10.1145/800133.804357.
  33. Walter J. Savitch (1970): Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), pp. 177–192, doi:10.1016/S0022-0000(70)80006-X.
  34. Zdenek Sawa (2010): Efficient construction of semilinear representations of languages accepted by unary NFA. In: Antonín Kucera & Igor Potapov: RP, Lecture Notes in Computer Science 6227. Springer, pp. 176–182, doi:10.1007/978-3-642-15349-5_12.
  35. J. C. Shepherdson (1959): The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), pp. 198 –200, doi:10.1147/rd.32.0198.
  36. Michael Sipser (1980): Lower bounds on the size of sweeping automata. J. Comput. Syst. Sci. 21(2), pp. 195–202, doi:10.1016/0022-0000(80)90034-3.
  37. Róbert Szelepcsényi (1988): The method of forced enumeration for nondeterministic automata. Acta Inf. 26(3), pp. 279–284, doi:10.1007/BF00299636.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org