Limited Automata and Context-Free Languages

• Autorzy: Pighizzini G. , Pisoni A.

Identyfikatory

DOI

10.3233/FI-2015-1148

• Języki publikacji: EN

Abstrakty

EN

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2- limited automata coincides with the class of deterministic context-free languages.

Słowa kluczowe

EN

finite automata; formal languages; turing machines; deterministic context-free languages; descriptional complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 1/2
• Strony: 157--176
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Pighizzini G.

• Dipartimento di Informatica Universit`a degli Studi di Milano via Comelico 39, 20135 Milano, Italy

autor

Pisoni A.

• Dipartimento di Informatica Universit`a degli Studi di Milano via Comelico 39, 20135 Milano, Italy

Bibliografia

• [1] Blum, N., Koch, R.: Greibach Normal Form Transformation Revisited, Information and Computation, 150(1), 1999, 112–118, ISSN 0890-5401.
• [2] Chomsky, N., Schützenberger, M.: The Algebraic Theory of Context-Free Languages, in: Computer Programming and Formal Systems (P. Braffort, D. Hirschberg, Eds.), vol. 35 of Studies in Logic and the Foundations of Mathematics, Elsevier, 1963, 118–161.
• [3] Goldstine, J., Kappes, M., Kintala, C. M. R., Leung, H., Malcher, A., Wotschke, D.: Descriptional Complexity of Machines with Limited Resources, J. UCS, 8(2), 2002, 193–234.
• [4] Harrison, M. A.: Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1978, ISBN 0201029553.
• [5] Hibbard, T. N.: A Generalization of Context-Free Determinism, Information and Control, 11(1/2), 1967, 196–238.
• [6] Holzer, M., Kutrib, M.: Descriptional Complexity — An Introductory Survey, in: Scientific Applications of Language Methods, chapter 1, Imperial College Press, 2010, 1–58.
• [7] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
• [8] Pighizzini, G., Pisoni, A.: Limited Automata and Regular Languages, in: Descriptional Complexity of Formal Systems (H. Jürgensen, R. Reis, Eds.), vol. 8031 of Lecture Notes in Computer Science, Springer, 2013, 253–264, An extended version will appear on the International Journal of Foundations of Computer Science.
• [9] Pighizzini, G., Shallit, J., Wang, M.: Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds, J. Computer and System Sciences, 65(2), 2002, 393–414.
• [10] Shallit, J. O.: A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2008.
• [11] Wagner, K.W.,Wechsung, G.: Computational Complexity, D. Reidel Publishing Company, Dordrecht, 1986