Two-Way Finite Automata: Old and Recent Results

• Autorzy: Pighizzini G.
• Języki publikacji: EN

Abstrakty

EN

The notion of two-way automata was introduced at the very beginning of automata theory. In 1959, Rabin and Scott and, independently, Shepherdson, proved that these models, both in the deterministic and in the nondeterministic versions, have the same power of one-way automata, namely, they characterize the class of regular languages. In 1978, Sakoda and Sipser posed the question of the costs, in the number of the states, of the simulations of one-way and two-way non-deterministic automata by two-way deterministic automata. They conjectured that these costs are exponential. In spite of all attempts to solve it, this question is still open. In the last ten years the problem of Sakoda and Sipser was widely reconsidered and many new results related to it have been obtained. In this work we discuss some of them. In particular, we focus on the restriction to the unary case, namely the case of automata defined over the one letter input alphabet, and on the connections with open questions in space complexity.

Słowa kluczowe

EN

descriptional complexity; space complexity; two-way finite automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 2-3
• Strony: 225--246
• Opis fizyczny: Bibliogr. 47 poz.

Twórcy

autor

Pighizzini G.

• Dipartimento di Informatica, Università degli Studi di Milano, Italia

Bibliografia

• [1] Balcerzak, M., Niwinski, D.: Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal, Inf. Process. Lett., 110(10), 2010, 396-398.
• [2] Berman, P.: A note on sweeping automata, in: Automata, Languages and Programming (J. de Bakker, J. van Leeuwen, Eds.), vol. 85 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1980, 91-97.
• [3] Berman, P., Lingas, A.: On the complexity of regular languages in terms of finite automata, Technical Report 304, Polish Academy of Sciences, 1977.
• [4] Bertoni, A., Mereghetti, C., Pighizzini, G.: An Optimal Lower Bound for Nonregular Languages, Inf. Process. Lett., 50(6), 1994, 289-292, Errata: [5].
• [5] Bertoni, A., Mereghetti, C., Pighizzini, G.: Corrigendum: An Optimal Lower Bound for Nonregular Languages, Inf. Process. Lett., 52(6), 1994, 339.
• [6] Chen, J., Yap, C.-K.: Reversal Complexity, SIAM J. Comput., 20(4), 1991, 622-638.
• [7] Chrobak, M.: Finite automata and unary languages, Theor. Comput. Sci., 47(3), 1986, 149-158, Errata: [8].
• [8] Chrobak, M.: Errata to: Finite automata and unary languages: [Theoret. Comput. Sci. 47 (1986) 149-158], Theor. Comput. Sci., 302(1-3), 2003, 497 - 498.
• [9] Gawrychowski, P.: Chrobak Normal Form Revisited, with Applications, in: Implementation and Application of Automata (B. Bouchou-Markhoff, P. Caron, J.-M. Champarnaud, D. Maurel, Eds.), vol. 6807 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2011, 142-153.
• [10] Geffert, V.: Magic numbers in the state hierarchy of finite automata, Inf. Comput., 205(11), 2007, 1652-1670.
• [11] Geffert, V., Guillon, B., Pighizzini, G.: Two-Way Automata Making Choices Only at the Endmarkers, in: Language and Automata Theory and Applications (A.-H. Dediu, C. Martin-Vide, Eds.), vol. 7183 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2012, 264-276.
• [12] Geffert, V., Mereghetti, C., Pighizzini, G.: Sublogarithmic Bounds on Space and Reversals, SIAMJ. Comput., 28(1), 1998, 325-340.
• [13] Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata, Theor. Comput. Sci., 295, 2003, 189-203.
• [14] Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata, Inf. Comput., 205(8), 2007, 1173-1187.
• [15] Geffert, V., Pighizzini, G.: Two-way unary automata versus logarithmic space, Inf. Comput., 209(7), 2011, 1016-1025.
• [16] Hardy, G., Wright, E.: An Introduction to the Theory of Numbers, Oxford Science Pub., 1979.
• [17] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Addison- Wesley, 1979.
• [18] Hromkovic, J., Schnitger, G.: Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipsers Separation, in: Automata, Languages and Programming (J. Baeten, J. Lenstra, J. Parrow, G. Woeginger, Eds.), vol. 2719 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2003, 193-193.
• [19] Ibarra, O. H.: A Note on Semilinear Sets and Bounded-Reversal Multihead Pushdown Automata, Inf. Process. Lett., 3(1), 1974, 25-28.
• [20] Ibarra, O. H.: Reversal-Bounded Multicounter Machines and Their Decision Problems, J. ACM, 25(1), 1978, 116-133.
• [21] Immerman, N.: Nondeterministic space is closed under complementation, SIAM J. Comput., 17(5), 1988, 935-938.
• [22] Kapoutsis, C.: Removing Bidirectionality from Nondeterministic Finite Automata, in: Mathematical Foundations of Computer Science 2005 (J. Jedrzejowicz, A. Szepietowski, Eds.), vol. 3618 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2005, 544-555.
• [23] Kapoutsis, C.: Two-Way Automata versus Logarithmic Space, in: Computer Science Theory and Applications (A. Kulikov, N. Vereshchagin, Eds.), vol. 6651 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2011, 359-372.
• [24] Kapoutsis, C.: Minicomplexity, in: Descriptional Complexity of Formal Systems (M. Kutrib, N. Moreira, R. Reis, Eds.), vol. 7386 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2012, 20-42.
• [25] Kapoutsis, C., Pighizzini, G.: Reversal Hierarchies for Small 2DFAs, in: Mathematical Foundations of Computer Science 2012 (B. Rovan, V. Sassone, P. Widmayer, Eds.), vol. 7464 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2012, 554-565.
• [26] Kapoutsis, C., Pighizzini, G.: Two-Way Automata Characterizations of L/poly versus NL, in: Computer Science, Theory and Applications (E. Hirsch, J. Karhumaki, A. Lepisto, M. Prilutskii, Eds.), vol. 7353 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2012, 217-228.
• [27] Kapoutsis, C. A.: Nondeterminism is essential in small two-way finite automata with few reversals, Information and Computation, 222, 2013, 208 - 227.
• [28] Kapoutsis, C. A., Kralovic, R., Momke, T.: Size complexity of rotating and sweeping automata, J. Comput. Syst. Sci, 78(2), 2012, 537-558.
• [29] Karp, R., Lipton, R.: Turing machines that take advice, in: Logic and Algorithmic (E. Engeler et al, Ed.), L’Enseignement Mathematique, Geneve, 1982, 191-209.
• [30] Kunc, M., Okhotin, A.: Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups, in: Developments in Language Theory (G. Mauri, A. Leporati, Eds.), vol. 6795 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2011, 324-336.
• [31] Kutrib, M., Malcher, A., Pighizzini, G.: Oblivious Two-Way Finite Automata: Decidability and Complexity, in: LATIN 2012: Theoretical Informatics (D. Fernandez-Baca, Ed.), vol. 7256 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2012, 518-529.
• [32] Lupanov, O.: A comparison of two types of finite automata, Problemy Kibernet, 9, 1963, 321-326, (in Russian). German translation: Uber den Vergleich zweier Typen endlicher Quellen, Probleme der Kybernetik 6, 329-335 (1966).
• [33] Malcher, A., Mereghetti, C., Palano, B.: Descriptional complexity of two-way pushdown automata with restricted head reversals, Theor. Comput. Sci., 449, 2012, 119-133.
• [34] Mereghetti, C.: Testing the descriptional power of small Turing machines on nonregular language acceptance, Int. J. Found. Comput. Sci., 19(4), 2008, 827-843.
• [35] Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata, SIAM J. Comput., 30(6), 2001, 1976-1992.
• [36] Meyer, A. R., Fischer, M. J.: Economy of description by automata, grammars, and formal systems, SWAT ’71: Proceedings of the 12th Annual Symposium on Switching and Automata Theory, IEEE Computer Society, Washington, DC, USA, 1971.
• [37] Micali, S.: Two-way deterministic finite automata are exponentially more succinct than sweeping automata, Inf. Process. Lett., 12(2), 1981, 103-105.
• [38] Moore, F.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondetermin- istic, and two-way finite automata, Computers, IEEE Transactions on, C-20(10), 1971, 1211 - 1214.
• [39] Rabin, M. O., Scott, D.: Finite automata and their decision problems, IBM J. Res. Dev., 3(2), 1959, 114-125.
• [40] Reinhardt, K., Allender, E.: Making Nondeterminism Unambiguous, SIAM Journal on Computing, 29(4), 2000, 1118-1131.
• [41] Sakoda, W. J., Sipser, M.: Nondeterminism and the size of two-way finite automata, STOC (R. J. Lipton, W. A. Burkhard, W. J. Savitch, E. P. Friedman, A. V. Aho, Eds.), ACM, 1978.
• [42] Savitch, W. J.: Relationships between nondeterministic and deterministic tape complexities, J. Comput. Syst. Sci., 4(2), 1970, 177-192.
• [43] Sawa, Z.: Efficient Construction of Semilinear Representations of Languages Accepted by Unary Nondeterministic Finite Automata, Fundamenta Informaticae, 123(1), 2013, 97-106.
• [44] Shepherdson, J. C.: The reduction of two-way automata to one-way automata, IBM J. Res. Dev., 3(2), 1959, 198 -200.
• [45] Sipser, M.: Halting Space-Bounded Computations, Theor. Comput. Sci., 10, 1980, 335-338.
• [46] Sipser, M.: Lower bounds on the size of sweeping automata, J. Comput. Syst. Sci., 21(2), 1980, 195-202.
• [47] Szelepcsenyi, R.: The method of forced enumeration for nondeterministic automata, Acta Inf., 26(3), 1988, 279-284.