Abstract
This is a talk on the size complexity of two-way finite automata. We present the central open problem in the area, explain a motivation behind it, recall its early history, and introduce some of the concepts used in its study. We then sketch a possible future, describe a natural systematic way of pursuing it, and record some of the progress that has been achieved. We add little to what is already known—only exposition, terminology, and questions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
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)
Birget, J.-C.: Two-way automata and length-preserving homomorphisms. Report 109, Department of Computer Science, University of Nebraska (1990)
Birget, J.-C.: State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical Systems Theory 26, 237–269 (1993)
Chrobak, M.: Finite automata and unary languages. Theoretical Computer Science 47, 149–158 (1986)
Dwork, C., Stockmeyer, L.J.: A time complexity gap for two-way probabilistic finite-state automata. SIAM Journal of Computing 19(6), 1011–1023 (1990)
Dwork, C., Stockmeyer, L.J.: Finite state verifiers I: The power of interaction. Journal of the ACM 39(4), 800–828 (1992)
Freivalds, R.: Probabilistic two-way machines. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp. 33–45 (1981)
Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theoretical Computer Science 295, 189–203 (2003)
Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Information and Computation 205(8), 1173–1187 (2007)
Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. Journal of Universal Computer Science 8(2), 193–234 (2002)
Hromkovič, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Information and Computation 169, 284–296 (2001)
Hromkovič, J., Schnitger, G.: Nondeterminism versus determinism for two-way finite automata: generalizations of Sipser’s separation. In: Proceedings of the International Colloquium on Automata, Languages, and Programming, pp. 439–451 (2003)
Kapoutsis, C.: Small sweeping 2NFAs are not closed under complement. In: Proceedings of the International Colloquium on Automata, Languages, and Programming, pp. 144–156 (2006)
Kapoutsis, C.: Deterministic moles cannot solve liveness. Journal of Automata, Languages and Combinatorics 12(1-2), 215–235 (2007)
Kapoutsis, C., Královič, R., Mömke, T.: An exponential gap between Las Vegas and deterministic sweeping finite automata. In: Proceedings of the International Symposium on Stochastic Algorithms: Foundations and Applications, pp. 130–141 (2007)
Kapoutsis, C., Královič, R., Mömke, T.: On the size complexity of rotating and sweeping automata. In: Proceedings of the International Conference on Developments in Language Theory, pp. 455–466 (2008)
Královič, R.: Infinite vs. finite space-bounded randomized computations. In: Proceedings of the IEEE Conference on Computational Complexity (to appear, 2009)
Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM Journal of Computing 13(1), 135–155 (1984)
Macarie, I.I., Seiferas, J.I.: Amplification of slight probabilistic advantage at absolutely no cost in space. Information Processing Letters 72(3–4), 113–118 (1999)
Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proceedings of the Symposium on Switching and Automata Theory, pp. 188–191 (1971)
Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Reading (1994)
Rabin, M.O.: Two-way finite automata. In: Proceedings of the Summer Institute of Symbolic Logic, Cornell, pp. 366–369 (1957)
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM Journal of Research and Development 3, 114–125 (1959)
Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of the Symposium on the Theory of Computing, pp. 275–286 (1978)
Seiferas, J.I.: Untitled manuscript. Communicated to M. Sipser (October 1973)
Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM Journal of Research and Development 3, 198–200 (1959)
Sipser, M.: Halting space-bounded computations. Theoretical Computer Science 10, 335–338 (1980)
Sipser, M.: Lower bounds on the size of sweeping automata. Journal of Computer and System Sciences 21(2), 195–202 (1980)
Sipser, M.: Introduction to the theory of computation. PWS Publishing Company, Boston (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kapoutsis, C.A. (2009). Size Complexity of Two-Way Finite Automata. In: Diekert, V., Nowotka, D. (eds) Developments in Language Theory. DLT 2009. Lecture Notes in Computer Science, vol 5583. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02737-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-02737-6_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02736-9
Online ISBN: 978-3-642-02737-6
eBook Packages: Computer ScienceComputer Science (R0)