Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems

• Autorzy: Ivanov S. , Verlan S.

Identyfikatory

DOI

10.3233/FI-2017-1580

• Języki publikacji: EN

Abstrakty

EN

In this article, we consider leftist insertion-deletion systems (LIDS), in which all rules have contexts on the same (left) side, and may only insert or delete one symbol at a time. We start by introducing extended rules, in which the contexts may be specified as regular expressions, instead of fixed words. We prove that in this case the computational completeness is achieved when additional control mechanisms are used (graph control with two states, matrix control with binary matrices and random-context control). We then show how rules with regular contexts can be simulated by conventional rules checking one-symbol (resp. two-symbol) left contexts for insertion and two-symbol (resp. one-symbol) left contexts for deletion. This simulation does not generally hold in the controlled case, however. Hence, we provide a construction simulating an arbitrary 2-tag system using extended rules and which can be rewritten in terms of conventional rules of types above, which implies that the latter systems are universal.

Słowa kluczowe

EN

graph theory; binary system; quotient rule; messenger RNA; RNA editing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 163--185
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Ivanov S.

• Université Paris Est, LACL (EA 4219), UPEC, F-94010, Créteil, France

autor

Verlan S.

• Université Paris Est, LACL (EA 4219), UPEC, F-94010, Créteil, France

Bibliografia

• [1] Marcus S. Contextual Grammars. Revue Roumaine de Mathématiques Pures et Appliquées, 1969;14: 1525–1534.
• [2] Pǎun Gh. Marcus Contextual Grammars. Kluwer Academic Publishers, Norwell, MA, USA, 1997. ISBN:0792347838.
• [3] Pǎun Gh, My NX. On the inner contextual grammars. Revue Roumaine de Mathématiques Pures et Appliqu ées, 1980;25:641–651.
• [4] Galiukschov B. Semicontextual Grammars. Matematicheskaya Logica i Matematicheskaya Lingvistika, 1981; pp. 38–50. Tallin University. (In Russian).
• [5] Haussler D. Insertion and Iterated Insertion as Operations on Formal Languages. Ph.D. thesis, University of Colorado at Boulder, 1982.
• [6] Haussler D. Insertion Languages. Information Sciences, 1983;31(3):77–89. URL https://doi.org/10.1016/0020-0255(83)90023-3.
• [7] Kleene SC. Representation of Events in Nerve Nets and Finite Automata. In: Shannon C, McCarthy J (eds.), Automata Studies, pp. 3–41. Princeton University Press, Princeton, NJ, 1956.
• [8] Kari L. On Insertion and Deletion in Formal Languages. Ph.D. thesis, University of Turku, 1991.
• [9] Kari L, Thierrin G. Contextual Insertions/Deletions and Computability. Information and Computation, 1996;131(1):47–61. URL https://doi.org/10.1006/inco.1996.0091.
• [10] Daley M, Kari L, Gloor G, Siromoney R. Circular Contextual Insertions/Deletions with Applications to Biomolecular Computation. In: SPIRE/CRIWG. 1999 pp. 47–54. ISBN:0-7695-0268-7.
• [11] Kari L, Pǎun Gh, Thierrin G, Yu S. At the Crossroads of DNA Computing and Formal Languages: Characterizing RE Using Insertion-Deletion Systems. In: Proceedings of 3rd DIMACS Workshop on DNA Based Computing. Philadelphia, 1997 pp. 318–333.
• [12] Pǎun Gh, Rozenberg G, Salomaa A. DNA Computing: New Computing Paradigms. Springer, 1998. ISBN:3540641963.
• [13] Takahara A, Yokomori T. On the Computational Power of Insertion-Deletion Systems. In: Hagiya M, Ohuchi A (eds.), DNA Computing, 8th International Workshop on DNA Based Computers, DNA8, Sapporo, Japan, June 10-13, 2002, Revised Papers, volume 2568 of Lecture Notes in Computer Science. Springer, 2002 pp. 269–280. ISBN:3-540-00531-5.
• [14] Margenstern M, Pǎun Gh, Rogozhin Yu, Verlan S. Context-Free Insertion-Deletion Systems. Theoretical Computer Science, 2005;330(2):339–348. URL https://doi.org/10.1016/j.tcs.2004.06.031.
• [15] Verlan S. On Minimal Context-Free Insertion-Deletion Systems. Journal of Automata, Languages and Combinatorics, 2007;12(1-2):317–328. URL http://dl.acm.org/citation.cfm?id=1463362.1463382.
• [16] Krassovitskiy A. Complexity and Modeling Power of Insertion-Deletion Systems. Ph.D. thesis, Departament de Filologies Rom´aniques, Universitat Rovira and Virgili, 2011. URL http://hdl.handle.net/10803/48631.
• [17] Verlan S. Study of Language-Theoretic Computational Paradigms Inspired by Biology. Habilitation thesis, Université Paris Est, 2010.
• [18] Benne R. RNA Editing: The Alteration of Protein Coding Sequences of RNA. Ellis Horwood, Chichester, West Sussex, 1993. ISBN-10: 0137825587.
• [19] Biegler F, Burrell MJ, Daley M. Regulated RNA Rewriting: Modelling RNA Editing with Guided Insertion. Theoretical Computer Science, 2007;387(2):103–112. doi:10.1016/j.tcs.2007.07.030.
• [20] Krassovitskiy A, Rogozhin Yu, Verlan S. Further Results on Insertion-Deletion Systems with One-Sided Contexts. In: Martín-Vide C, Otto F, Fernau H (eds.), Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers, volume 5196 of Lecture Notes in Computer Science. Springer, 2008 pp. 333–344. doi:10.1007/978-3-540-88282-4_31.
• [21] Krassovitskiy A, Rogozhin Yu, Verlan S. Computational power of insertion-deletion (P) systems with rules of size two. Natural Computing, 2011;10(2):835–852. doi:10.1007/s11047-010-9208-y. URL http://dx.doi.org/10.1007/s11047-010-9208-y.
• [22] Matveevici A, Rogozhin Yu, Verlan S. Insertion-Deletion Systems with One-Sided Contexts. In: Durand-Lose J, Margenstern M (eds.), Machines, Computations, and Universality, 5th International Conference, MCU 2007, Orléans, France, September 10-13, 2007, Proceedings, volume 4664 of Lecture Notes in Computer Science. Springer, 2007 pp. 205–217. doi:10.1007/978-3-540-74593-8_18.
• [23] Petre I, Verlan S. Matrix Insertion-Deletion Systems. Theoretical Computer Science, 2012;456(0):80–88. doi:10.1016/j.tcs.2012.07.002. URL http://www.sciencedirect.com/science/article/pii/S0304397512006470.
• [24] 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. URL http://dx.doi.org/10.3233/FI-2015-1203.
• [25] Freund R, Kogler M, Rogozhin Yu, Verlan S. Graph-Controlled Insertion-Deletion Systems. In: McQuillan I, Pighizzini G (eds.), Proceedings of the Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, volume 31 of EPTCS. 2010 pp. 88–98. doi:10.4204/EPTCS.31.11.
• [26] Ivanov S, Verlan S. About One-Sided One-Symbol Insertion-Deletion P Systems. In: Alhazov A, Cojocaru S, Gheorghe M, Yu Rogozhin, Rozenberg G, Salomaa A (eds.), Membrane Computing–14th International Conference, CMC 2013, Chis¸inǎu, Republic of Moldova, August 20-23, 2013, Revised Selected Papers, volume 8340 of Lecture Notes in Computer Science. Springer, 2013 pp. 225–237. doi:10.1007/978-3-642-54239-8_16.
• [27] Ivanov S, Verlan S. On the Lower Bounds for Leftist Insertion-Deletion Languages. Annals of the University of Bucharest (Informatics). 2015;LXII(2):77–88. URL http://www.lacl.fr/verlan/data/articles/insdelreg2.pdf.
• [28] Ivanov S. On the Power and Universality of Biologically-inspired Models of Computation. Ph.D. thesis, University of Paris Est, 2015.
• [29] Cocke J, Minsky M. Universality of Tag Systems with P = 2. Journal of the ACM, 1964. 11(1):15–20. doi:10.1145/321203.321206. URL http://doi.acm.org/10.1145/321203.321206.
• [30] Minsky M. Computations: Finite and Infinite Machines. Prentice Hall, Englewood Cliffts, NJ, 1967. ISBN:0-13-165563-9.
• [31] Ivanov S, Verlan S. Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States. In: Durand-Lose J, Nagy B (eds.), Machines, Computations, and Universality-7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings, volume 9288 of Lecture Notes in Computer Science. Springer, 2015 pp. 79–93. doi:10.1007/978-3-319-23111-2_6. URL http://dx.doi.org/10.1007/978-3-319-23111-2_6.
• [32] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages. Springer-Verlag, Berlin, 1997. ISBN:978-3-642-59136-5. doi:10.1007/978-3-642-59136-5.