Strongly Limited Automata

• Autorzy: Pighizzini G.

Identyfikatory

DOI

10.3233/FI-2016-1439

• 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. When d ≥2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call strongly limited automata, where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa.

Słowa kluczowe

EN

turing machines; computational complexity; machine theory; polynomials; formal languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 148, nr 3/4
• Strony: 369--392
• Opis fizyczny: Bibliogr. 19 poz., tab.

Twórcy

autor

Pighizzini G.

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

Bibliografia

• [1] Hibbard TN. A Generalization of Context-Free Determinism. Information and Control. 1967;11(1-2):196–238. doi:10.1016/S0019-9958(67)90513-X.
• [2] Wagner KW, Wechsung G. Computational Complexity. Dordrecht: D. Reidel Publishing Company; 1986.
• [3] Pighizzini G, Pisoni A. Limited Automata and Context-Free Languages. Fundam Inform. 2015;136(1-2):157–176. Available from: http://dx.doi.org/10.3233/FI-2015-1148. doi:10.3233/FI-2015-1148.
• [4] Pighizzini G, Pisoni A. Limited Automata and Regular Languages. Int J Found Comput Sci. 2014;25(7):897–916. Available from: http://dx.doi.org/10.1142/S0129054114400140. doi:10.1142/S0129054114400140.
• [5] Chomsky N, Schützenberger MP. The Algebraic Theory of Context-Free Languages. In: Braffort P, Hirschberg D, editors. Computer Programming and Formal Systems. vol. 35 of Studies in Logic and the Foundations of Mathematics. Elsevier; 1963. p. 118–161. Available from: http://dx.doi.org/10.1016/S0049-237X(08)72023-8.
• [6] Okhotin A. Non-erasing Variants of the Chomsky-Schützenberger Theorem. In: Yen H, Ibarra OH, editors. Developments in Language Theory - 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings. vol. 7410 of Lecture Notes in Computer Science. Springer; 2012. p. 121–129. Available from: http://dx.doi.org/10.1007/978-3-642-31653-1\_12. doi:10.1007/978-3-642-31653-1_12.
• [7] Jancar P, Mráz F, Plátek M. Forgetting Automata and Context-Free Languages. Acta Inf. 1996;33(5):409–420. doi:10.1007/s002360050050.
• [8] Glöckler J. Forgetting Automata and Unary Languages. Int J Found Comput Sci. 2007;18(4):813–827. Available from: http://dx.doi.org/10.1142/S0129054107004991. doi:10.1142/S0129054107004991.
• [9] Glöckler J. A Taxonomy of Deterministic Forgetting Automata. Int J Found Comput Sci. 2010; 21(4):619–631. Available from: http://dx.doi.org/10.1142/S0129054110007453. doi:10.1142/S0129054110007453.
• [10] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages and Computation. Addison-Wesley; 1979. ISBN: 020102988X, 9780201029888.
• [11] Shallit JO. A Second Course in Formal Languages and Automata Theory. Cambridge University Press; 2008. ISBN: 0521865727, 9780521865722.
• [12] McNaughton R, Papert SA. Counter-Free Automata (M.I.T. Research Monograph No. 65). The MIT Press; 1971. ISBN: 0262130769.
• [13] Goldstine J, Kappes M, Kintala CMR, Leung H, Malcher A, Wotschke D. Descriptional Complexity of Machines with Limited Resources. J UCS. 2002;8(2):193–234.
• [14] Holzer M, Kutrib M. Descriptional Complexity — An Introductory Survey. In: Scientific Applications of Language Methods. Imperial College Press; 2010. p. 1–58. doi:10.1142/9781848165458_0001.
• [15] Kutrib M, Pighizzini G. Recent trends in descriptional complexity of formal languages. EATCS Bulletin. 2013;111:70–86.
• [16] Harrison MA. Introduction to Formal Language Theory. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.; 1978. ISBN: 0201029553.
• [17] Rosenkrantz DJ. Matrix Equations and Normal Forms for Context-Free Grammars. J ACM. 1967; 14(3):501–507. doi:10.1145/321406.321412.
• [18] Engelfriet J. An Elementary Proof of Double Greibach Normal Form. Inf Process Lett. 1992;44(6):291–293. doi:10.1016/0020-0190(92)90101-Z.
• [19] Yoshinaka R. An elementary proof of a generalization of double Greibach normal form. Inf Process Lett. 2009;109(10):490–492. Available from: http://dx.doi.org/10.1016/j.ipl.2009.01.015.doi:10.1016/j.ipl.2009.01.015.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).