Random Context and Semi-conditional Insertion-deletion Systems

• Autorzy: Ivanov S. , Verlan S.

Identyfikatory

DOI

10.3233/FI-2015-1203

• Języki publikacji: EN

Abstrakty

EN

In this article we introduce the operations of insertion and deletion working in random context and semi-conditional modes. We show that conditional application of insertion and deletion rules strictly increases the computational power. In the case of semi-conditional insertion-deletion systems, context-free insertion and deletion rules of one symbol are sufficient to achieve computational completeness. In the random context case, our results expose asymmetry between the computational power of insertion and deletion rules: semi-conditional systems of size (2, 0, 0; 1, 1, 0) (with context-free two-symbol insertion rules, and one-symbol deletion rules with one-symbol left context) are computationally complete, while systems of size (1, 1, 0; 2, 0, 0) (and, more generally, of size (1, 1, 0; p, 1, 1)) are not.

Słowa kluczowe

EN

insertion deletion; random context; computational completeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 127--144
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Ivanov S.

• Laboratoire d’Algorithmique, Complexité et Logique Université Paris Est – Créteil Val de Marne 61, av. gén. de Gaulle, 94010 Créteil, France

autor

Verlan S.

• Laboratoire d’Algorithmique, Complexité et Logique Université Paris Est – Créteil Val de Marne 61, av. gén. de Gaulle, 94010 Créteil, France

Bibliografia

• [1] A. Alhazov, A. Krassovitskiy, Yu. Rogozhin, and S. Verlan. Small Size Insertion and Deletion Systems. In C. Martin-Vide, ed., Scientific Applications of Language Methods, volume 2 of Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory, chap. 9, 459–524.World Scientific, 2010.
• [2] A. Alhazov, A. Krassovitskiy, Yu. Rogozhin, and S. Verlan. P Systems with Minimal Insertion and Deletion. Theoretical Computer Science, 412(1-2):136–144, 2011.
• [3] R. Benne. RNA Editing: The Alteration of Protein Coding Sequences of RNA. Ellis Horwood, Chichester, West Sussex, 1993.
• [4] F. Biegler, M. J. Burrell, and M. Daley. Regulated RNA Rewriting: Modelling RNA Editing with Guided Insertion. Theoretical Computer Science, 387(2):103 – 112, 2007.
• [5] E. Csuhaj-Varjú and A. Salomaa. Networks of Parallel Language Processors. New Trends in Formal Languages - Control, Cooperation, and Combinatorics, vol. 1218 of LNCS, 299-318, Springer, 1997.
• [6] M. Daley, L. Kari, G. Gloor, and R. Siromoney. Circular Contextual Insertions/Deletions with Applications to Biomolecular Computation. In SPIRE/CRIWG, 47–54, 1999.
• [7] J. Dassow and Gh. Paun. Regulated Rewriting in Formal Language Theory. Springer, Berlin, 1989.
• [8] R. Freund, M. Kogler, Yu. Rogozhin, and S. Verlan. Graph-controlled Insertion-deletion Systems. In I. Mc-Quillan and G. Pighizzini, eds., Proc. of 12th Workshop on Descriptional Complexity of Formal Systems, vol. 31 of EPTCS, 88–98, 2010.
• [9] B. Galiukschov. Semicontextual Grammars. Matematicheskaya Logica i Matematicheskaya Lingvistika, 38–50, 1981. Tallin University (in Russian).
• [10] V. Geffert. Normal Forms for Phrase-structure Grammars. ITA, 25:473–498, 1991.
• [11] D. Haussler. Insertion and Iterated Insertion as Operations on Formal Languages. PhD thesis, Univ. of Colorado at Boulder, 1982.
• [12] D. Haussler. Insertion Languages. Information Sciences, 31(1):77–89, 1983.
• [13] S. Ivanov, S. Verlan, Random Context and Semi-conditional Insertion-deletion Systems, arXiv, CoRR abs/1112.5947, 2011.
• [14] L. Kari. On Insertion and Deletion in Formal Languages. PhD thesis, University of Turku, 1991.
• [15] L. Kari, Gh. Păun, G. Thierrin, and S. Yu. At the Crossroads of DNA Computing and Formal Languages: Characterizing RE Using Insertion-deletion Systems. In Proc. of 3rd DIMACS Workshop on DNA Based Computing, 318–333. Philadelphia, 1997.
• [16] S. C. Kleene. Representation of Events in Nerve Nets and Finite Automata. In C. Shannon and J. McCarthy, eds., Automata Studies, 3–41. Princeton University Press, Princeton, NJ, 1956.
• [17] A. Krassovitskiy, Yu. Rogozhin, and S. Verlan. Further Results on Insertion-deletion Systems with Onesided Contexts. In C. Martın-Vide et al., eds., Language and Automata Theory and Applications, Second International Conference, LATA 2008. Revised Papers, vol. 5196 of LNCS, 333–344. Springer, 2008.
• [18] A. Krassovitskiy, Yu. Rogozhin, and S. Verlan. Computational Power of P Systems with Small Size Insertion and Deletion Rules. In T. Neary, D. Woods, A. K. Seda, and N. Murphy, eds., Proc. International Workshop on The Complexity of Simple Programs, Cork, Ireland, 6-7th December 2008, vol. 1 of EPTCS, 108–117, 2009.
• [19] A. Krassovitskiy, Yu. Rogozhin, and S. Verlan. Computational Power of Insertion-deletion (P) Systems with Rules of Size Two. Natural Computing, 10(2), 835–852, 2011.
• [20] S. Marcus. Contextual Grammars. Revue Roumaine de Math´ematiques Pures et Appliqu´ees, 14:1525–1534,1969.
• [21] M. Margenstern, Gh. Păun, Yu. Rogozhin, and S. Verlan. Context-free Insertion-deletion Systems. Theoretical Computer Science, 330(2):339–348, 2005.
• [22] A. Matveevici, Yu. Rogozhin, and S. Verlan. Insertion-deletion Systems with One-sided Contexts. In J. O. Durand-Lose and M. Margenstern, eds., Machines, Computations, and Universality, 5th International Conference, MCU 2007, Oréans, France, Proceedings, vol. 4664 of LNCS, 205–217, 2007.
• [23] I. Petre and S. Verlan. Matrix Insertion-deletion Systems. Theoretical Computer Science, 456:80–88 , 2012.
• [24] Gh. Păun. A Variant of Random Context Grammars: Semi-conditional Grammars. Theoretical Computer Science, 41:1-17, 1985.
• [25] Gh. Păun. Marcus Contextual Grammars. Kluwer Academic Publishers, Norwell, MA, USA, 1997.
• [26] Gh. Păun. Membrane Computing. An Introduction. Springer, 2002.
• [27] Gh. Păun, G. Rozenberg, and A. Salomaa. DNA Computing: New Computing Paradigms. Springer, 1998.
• [28] G. Rozenberg and A. Salomaa, eds. Handbook of Formal Languages. Springer, Berlin, 1997.
• [29] W. D. Smith. DNA Computers In Vitro and In Vivo. In R. Lipton and E. Baum, eds., Proceedings of DIMACS Workshop on DNA Based Computers, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 121–185. American Mathematical Society, 1996.
• [30] A. Takahara and T. Yokomori. On the Computational Power of Insertion-deletion Systems. In M. Hagiya and A. Ohuchi, eds., Proc. of 8th International Workshop on DNA Based Computers, Revised Papers, vol. 2568 of LNCS, 269–280, 2002.
• [31] S. Verlan. On Minimal Context-free Insertion-deletion Systems. Journal of Automata, Languages and Combinatorics, 12(1-2):317–328, 2007.
• [32] S. Verlan. Study of Language-theoretic Computational Paradigms Inspired by Biology. Habilitation thesis, University of Paris Est, 2010.