Minicomplexity

1. Barnes, B.H.: A two-way automaton with fewer states than any equivalent one-way automaton. IEEE Transactions on Computers C-20(4), 474–475 (1971)

   Article  Google Scholar 

2. Berman, P., Lingas, A.: On complexity of regular languages in terms of finite automata. Report 304, Institute of Computer Science, Polish Academy of Sciences, Warsaw (1977)

   Google Scholar 

3. Birget, J.C.: Two-way automata and length-preserving homomorphisms. Mathematical Systems Theory 29, 191–226 (1996)

   MathSciNet  MATH  Google Scholar 

4. Geffert, V.: An alternating hierarchy for finite automata. Theoretical Computer Science (to appear)

   Google Scholar 

5. Geffert, V., Guillon, B., Pighizzini, G.: Two-Way Automata Making Choices Only at the Endmarkers. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 264–276. Springer, Heidelberg (2012)

   Chapter  Google Scholar 

6. Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theoretical Computer Science 295, 189–203 (2003)

   Article  MathSciNet  MATH  Google Scholar 

7. Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Information and Computation 205(8), 1173–1187 (2007)

   Article  MathSciNet  MATH  Google Scholar 

8. Hromkovič, J., Schnitger, G.: Nondeterminism Versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 439–451. Springer, Heidelberg (2003)

   Chapter  Google Scholar 

9. Kapoutsis, C.A.: Nondeterminism is essential in small two-way finite automata with few reversals. Information and Computation (to appear)

   Google Scholar 

10. Kapoutsis, C.A.: Removing Bidirectionality from Nondeterministic Finite Automata. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 544–555. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

11. Kapoutsis, C.A.: Algorithms and lower bounds in finite automata size complexity. Phd thesis, Massachusetts Institute of Technology (June 2006)

    Google Scholar 

12. Kapoutsis, C.A.: Small Sweeping 2NFAs Are Not Closed Under Complement. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 144–156. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

13. Kapoutsis, C.A.: Deterministic moles cannot solve liveness. Journal of Automata, Languages and Combinatorics 12(1-2), 215–235 (2007)

    MathSciNet  MATH  Google Scholar 

14. Kapoutsis, C.A.: Size Complexity of Two-Way Finite Automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 47–66. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

15. Kapoutsis, C.A.: Two-Way Automata versus Logarithmic Space. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol. 6651, pp. 359–372. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

16. Kapoutsis, C.A., Královič, R., Mömke, T.: On the Size Complexity of Rotating and Sweeping Automata. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 455–466. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

17. Kapoutsis, C.A., Lefebvre, N.: Analogs of Fagin’s Theorem for small nondeterministic finite automata. In: Proceedings of DLT (to appear, 2012)

    Google Scholar 

18. Kapoutsis, C.A., Pighizzini, G.: Reversal hierarchies for small 2DFAs (submitted)

    Google Scholar 

19. Kapoutsis, C.A., Pighizzini, G.: Two-way automata characterizations of L/poly versus NL. In: Proceedings of CSR, pp. 222–233 (2012)

    Google Scholar 

20. Kozen, D.C.: Automata and computability. Springer (1997)

    Google Scholar 

21. Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proceedings of FOCS, pp. 188–191 (1971)

    Google Scholar 

22. Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on Computers 20(10), 1211–1214 (1971)

    Article  MATH  Google Scholar 

23. Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM Journal of Research and Development 3, 114–125 (1959)

    Article  MathSciNet  Google Scholar 

24. Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of STOC, pp. 275–286 (1978)

    Google Scholar 

25. Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences 4, 177–192 (1970)

    Article  MathSciNet  MATH  Google Scholar 

26. Seiferas, J.I.: Untitled (October 1973), manuscript

    Google Scholar 

27. Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM Journal of Research and Development 3, 198–200 (1959)

    Article  MathSciNet  Google Scholar 

28. Sipser, M.: Halting space-bounded computations. Theoretical Computer Science 10, 335–338 (1980)

    Article  MathSciNet  MATH  Google Scholar 

29. Sipser, M.: Lower bounds on the size of sweeping automata. Journal of Computer and System Sciences 21(2), 195–202 (1980)

    Article  MathSciNet  MATH  Google Scholar 

30. Sipser, M.: Introduction to the theory of computation. Thomson Course Technology, 2nd edn. (2006)

    Google Scholar 

31. Szepietowski, A.: If deterministic and nondeterministic space complexities are equal for loglogn then they are also equal for logn. In: Proceedings of STACS, pp. 251–255 (1989)

    Google Scholar 

Download references