Decidability Questions for Insertion Systems and Related Models

• Autorzy: Malcher Andreas

Identyfikatory

DOI

10.3233/FI-2021-2034

• Języki publikacji: EN

Abstrakty

EN

Insertion systems or insertion grammars are a generative formalism in which words can only be generated by starting with some axioms and by iteratively inserting strings subject to certain contexts of a fixed maximal length. It is known that languages generated by such systems are always context sensitive and that the corresponding language classes are incomparable with the regular languages. On the other hand, it is possible to generate non-semilinear languages with systems having contexts of length two. Here, we study decidability questions for insertion systems. On the one hand, it can be seen that emptiness and universality are decidable. Moreover, the fixed membership problem is solvable in deterministic polynomial time. On the other hand, the usually studied decidability questions such as, for example, finiteness, inclusion, equivalence, regularity, inclusion in a regular language, and inclusion of a regular language turn out to be undecidable. Interestingly, the latter undecidability results can be carried over to other models which are basically able to handle the mechanism of inserting strings depending on contexts. In particular, new undecidability results are obtained for pure grammars, restarting automata, clearing restarting automata, and forgetting automata.

Słowa kluczowe

EN

insertion systems; decidability questions; pure grammar; clearing restarting automata; restarting automata; forgetting automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 1-2
• Strony: 53--76
• Opis fizyczny: Bibliogr. 25 poz., tab.

Twórcy

autor

Malcher Andreas

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

Bibliografia

• [1] Galiukschov BS. Semicontextual Grammars (in Russian). Mat. Log. Mat. Ling., 1981. pp. 38-50.
• [2] Păun G. Marcus Contextual Grammars, volume 67 of Studies in Linguistics and Philosophy. Kluwer Academic Publishers, Dordrecht, 1997. ISBN:978-94-015-8969-7.
• [3] Păun G, Rozenberg G, Salomaa A. DNA Computing - New Computing Paradigms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1998.
• [4] Alhazov A, Krassovitskiy A, Rogozhin Y, Verlan S. Small Size Insertion and Deletion Systems. In: Martín-Vide C (ed.), Scientific Applications of Language Methods, pp. 459-524. Imperial College Press, 2010. doi:10.1142/9781848165458_0009.
• [5] Ivanov S, Verlan S. Random Context and Semi-Conditional Insertion-Deletion Systems. Fundam. Inform., 2015. 138(1-2):127-144. doi:10.3233/FI-2015-1203.
• [6] Ivanov S, Verlan S. Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems. Fundam. Inform., 2017. 155(1-2):163-185. doi:10.3233/FI-2017-1580.
• [7] Dahlhaus E, Warmuth MK. Membership for Growing Context-Sensitive Grammars is Polynomial. J. Comput. Syst. Sci., 1986. 33(3):456-472. doi:10.1016/0022-0000(86)90062-0.
• [8] Maurer HA, Salomaa A, Wood D. Pure Grammars. Inform. and Control, 1980. 44(1):47-72. doi:10.1016/S0019-9958(80)90131-X.
• [9] Harju T, Penttonen M. Some Decidability Problems of Sentential Forms. Intern. J. Computer Math., 1979. 7:95-107. doi:10.1080/00207167908803161.
• [10] Malcher A. Decidability Questions for Insertion Systems. In: Freund R, Mráz F, Průša D (eds.), Non-Classical Models of Automata and Applications (NCMA 2017). Österreichische Computer Gesellschaft, 2017 pp. 165-180.
• [11] Halava V, Harju T, Hirvensalo M, Karhumäki J. Post Correspondence Problem for Short Words. Inf. Process. Lett., 2008. 108(3):115-118. doi:10.1016/j.ipl.2008.04.013.
• [12] Minsky ML. Recursive Unsolvability of Post’s Problem of “Tag” and other Topics in Theory of Turing Machines. Ann. of Math. (2), 1961. 74:437-455. doi:10.2307/1970290.
• [13] Jančar P, Mráz F, Plátek M, Vogel J. Restarting Automata. In: Fundamentals of Computation Theory (FCT 1995), volume 965 of Lecture Notes in Computer Science. Springer, 1995 pp. 283-292. doi:10.1007/3-540-60249-6_60.
• [14] Otto F. Restarting Automata and Their Relations to the Chomsky Hierarchy. In: Ésik Z, Fülöp Z (eds.), Developments in Language Theory (DLT 2003), volume 2710 of Lecture Notes in Computer Science. 2003 pp. 55-74. doi:10.1007/3-540-45007-6_5.
• [15] Kutrib M, Otto F. On the Descriptional Complexity of the Window Size for Deleting Restarting Automata. Int. J. Found. Comput. Sci., 2013. 24(6):831-846. doi:10.1142/S0129054113400212.
• [16] Černo P, Mráz F. Clearing Restarting Automata. Fundam. Inform., 2010. 104(1-2):17-54. doi:10.3233/FI-2010-334.
• [17] Vorel V. Synchronization, Road Coloring, and Jumps in Finite Automata. Master’s thesis, Charles University, Prague, Czech Republic, 2015. ID:215960177.
• [18] Černo P, Mráz F. Δ-Clearing Restarting Automata and CFL. In: Mauri G, Leporati A (eds.), Developments in Language Theory (DLT 2011), volume 6795 of Lecture Notes in Computer Science. Springer, 2011 pp. 153-164. doi:10.1007/978-3-642-22321-1_14.
• [19] Otto F, Černo P, Mráz F. On the Classes of Languages Accepted by Limited Context Restarting Automata. RAIRO - Theor. Inf. and Applic., 2014. 48(1):61-84. doi:10.1051/ita/2014001.
• [20] Jančar P, Mráz F, Plátek M. Forgetting Automata and the Chomsky Hierarchy. In: Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 1992). Masaryk University, Brno, 1992 pp. 41-44.
• [21] Fernau H, Kuppusamy L, Verlan S. Universal Matrix Insertion Grammars with Small Size. In: Patitz MJ, Stannett M (eds.), Unconventional Computation and Natural Computation (UCNC 2017), volume 10240 of LNCS. Springer, 2017 pp. 182-193. doi:10.1007/978-3-319-58187-3_14.
• [22] Biegler F, Burrell MJ, Daley M. Regulated RNA Rewriting: Modelling RNA Editing with Guided Insertion. Theor. Comput. Sci., 2007. 387(2):103-112. doi:10.1016/j.tcs.2007.07.030.
• [23] Freund R, Kogler M, Rogozhin Y, Verlan S. Graph-Controlled Insertion-Deletion Systems. In: McQuillan I, Pighizzini G (eds.), Descriptional Complexity of Formal Systems, (DCFS 2010), volume 31 of EPTCS. 2010 pp. 88-98. doi:10.4204/EPTCS.31.11.
• [24] Fernau H, Kuppusamy L, Raman I. On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes. J. Autom. Lang. Comb., 2017. 22(1-3):61-92. doi:10.25596/jalc-2017-061.
• [25] Fernau H, Kuppusamy L, Raman I. On the Computational Completeness of Graph-Controlled Insertion-Deletion Systems with Binary Sizes. Theor. Comput. Sci., 2017. 682:100-121. doi:10.1016/j.tcs.2017.01.019.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).