On Szilard Languages of Labelled Insertion Grammars

• Autorzy: Prithwinee, Paul
• Języki publikacji: EN

Abstrakty

EN

In this work we initiate the study of Szilard languages of labelled insertion grammars. It is well-known that there exist context-free languages which cannot be generated by any insertion grammar. We show that there exist some regular languages which cannot be Szilard language of any labelled insertion grammar. But any regular language can be given as a homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 1. Also, any context-free language can be obtained as a homomorphic image of Szilard language of a labelled insertion grammar of weight 2. We show that even though insertion grammars of weight 1 can generate only context-free languages, there exists some context-sensitive language which can be obtained as Szilard language of a labelled insertion grammar of weight 1. At the end we show that any recursively enumerable language can be characterized by the homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 5.

Słowa kluczowe

EN

Chomsky hierarchy; insertion grammar; Labelled insertion grammar; Szilard languages

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 172, nr 1
• Strony: 53--72
• Opis fizyczny: Bibliogr. 30 poz.

Twórcy

autor

Prithwinee, Paul

• Electronics and Communication Sciences Unit, Indian Statistical Institute, Kolkata - 700108, India,

Bibliografia

• [1] Takahara A, Yokomori T. On the computational power of insertion-deletion systems. Natural Computing, 2003. 2(4):321-336. doi:10.1023/B:NACO.0000006769.27984.23.
• [2] Kari L, Păun G, Thierrin G, Yu S. At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. In: DNA Based Computers, Proceedings of a DIMACS Workshop, Philadelphia, Pennsylvania, USA, June 23-25. 1997, pp. 329-346.
• [3] Verlan S. Recent developments on insertion-deletion systems. Computer Science Journal of Moldova, 2010. 18(2):210-245.
• [4] Margenstern M, Păun G, Rogozhin Y, Verlan S. Context-free insertion-deletion systems. Theoretical Computer Science, 2005. 330(2):339-348. doi:10.1016/j.tcs.2004.06.031.
• [5] Păun G, Pérez-Jiménez MJ, Yokomori T. Representations and Characterizations of Languages in Chomsky Hierarchy by Means of Insertion-Deletion Systems. International Journal of Foundations of Computer Science, 2008. 19(4):859-871. URL https://doi.org/10.1142/S0129054108006005.
• [6] Verlan S. On Minimal Context-Free Insertion-Deletion Systems. Journal of Automata, Languages and Combinatorics, 2007. 12(1-2):317-328. doi:10.25596/jalc-2007-317.
• [7] Kari L, Thierrin G. Contextual Insertions/Deletions and Computability. Information and Computation, 1996. 131(1):47-61. doi:10.1006/inco.1996.0091.
• [8] Krassovitskiy A, Rogozhin Y, Verlan S. Further Results on Insertion-Deletion Systems with One-Sided Contexts. In: 2nd International Conference on Language and Automata Theory and Applications, LATA 2008, Tarragona, Spain, March 13-19. 2008, pp. 333-344. doi:10.1007/978-3-540-88282-4_31.
• [9] Matveevici A, Rogozhin Y, Verlan S. Insertion-Deletion Systems with One-Sided Contexts. In: Machines, Computations, and Universality, 5th International Conference on Machine, Computations and Universality, MCU 2007, Orléans, France, September 10-13. 2007, pp. 205-217. doi:10.1007/978-3-540-74593-8_18.
• [10] Galiukschov BS. Semicontextual grammars. Matematicheskaya Logica i Matematicheskaya Lingvistika, Kalinin University, 1981. pp. 38-50.
• [11] Kari L, Sosík P. On the weight of universal insertion grammars. Theoretical Computer Science, 2008. 396(1-3):264-270. doi:10.1016/j.tcs.2008.01.037.
• [12] Martín-Vide C, Păun G, Salomaa A. Characterizations of Recursively Enumerable Languages by Means of Insertion Grammars. Theoretical Computer Science, 1998. 205(1-2):195-205. doi:10.1016/S0304-3975(97)00079-0.
• [13] Păun G. On semicontextual grammars. Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, 1984. 28(76):63-68.
• [14] Păun G. Two theorems about Galiukschov semicontextual languages. Kybernetika, 1985. 21(5):360-365.
• [15] Marcus S. Contextual grammars. Revue Roumaine de Mathematiques Pures et Appliquees, 1969. 14:1525-1534.
• [16] Squier C. Semicontextual grammars: An example. Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, 1988. 32(80):167-170.
• [17] Păun G, Rozenberg G, Salomaa A. DNA Computing - New Computing Paradigms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1998. ISBN 978-3-540-64196-4. doi:10.1007/978-3-662-03563-4.
• [18] Onodera K. A note on homomorphic representation of recursively enumerable languages with insertion grammars. IPSJ Journal, 2003. 44(5):1424-1427.
• [19] Fernau H, Kuppusamy L, Verlan S. Universal Matrix Insertion Grammars with Small Size. In: 16th International Conference on Unconventional Computation and Natural Computation, UCNC 2017, Fayetteville, AR, USA, June 5-9. 2017, pp. 182-193. doi:10.1007/978-3-319-58187-3_14.
• [20] Krassovitskiy A. On the power of Insertion P Systems of small size. International Journal of Computers, Communications and Controls, 2011. 6(2):266-277. URL https://doi.org/10.15837/ijccc.2011.2.2175.
• [21] Alhazov A, Krassovitskiy A, Rogozhin Y, Verlan S. P Systems with Insertion and Deletion Exo-Operations. Fundamenta Informaticae, 2011. 110(1-4):13-28. doi:10.3233/FI-2011-525.
• [22] Mäkinen E. On homomorphic images of Szilard languages. International Journal of Computer Mathematics, 1986. 18:239-245. URL https://doi.org/10.1080/00207168608803492.
• [23] Cojocaru L, Mäkinen E. On the Complexity of Szilard Languages of Matrix Grammars. In: 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2011, Timisoara, Romania, September 26-29. 2011, pp. 339-347. doi:10.1109/SYNASC.2011.34.
• [24] Cojocaru L, Mäkinen E. On some derivation mechanisms and the complexity of their Szilard languages. Theoretical Computer Science, 2014. 537:87-96. doi:10.1016/j.tcs.2014.02.048.
• [25] Mäkinen E. On Context-Free and Szilard Languages. BIT, 1984. 24(2):164-170.
• [26] Cojocaru L, Mäkinen E. The Complexity of Szilard Languages of Matrix Grammars Revisited. Fundamenta Informaticae, 2013. 123(4):381-399. doi:10.3233/FI-2013-817.
• [27] Mahalingam K, Paul P, Mäkinen E. On Derivation Languages of a Class of Splicing Systems. Acta Cybernetica, 2018. 23(4):1-13. doi:10.14232/actacyb.23.4.2018.1.
• [28] Mahalingam K, Paul P, Song B, Pan L, Subramanian KG. Derivation languages of Splicing P systems. In: 12th International conference on Bio-inspired Computing: Theories and Applications, BICTA 2017, Harbin, China, December 1-3. 2017, pp. 487-501. URL https://doi.org/10.1007/978-981-10-7179-9_38.
• [29] Păun G. On some families of Szilard languages. Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, 1983. 27(75):259-265.
• [30] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages, Vol. 1: Word, Language, Grammar. Springer-Verlag, Berlin, Heidelberg, 1997. ISBN 3-540-60420-0.

Uwagi

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

Identyfikatory

DOI

10.3233/FI-2020-1892