On Characterizing Recursively Enumerable Languages by Insertion Grammars

• Autorzy: Mutyam M. , Krithivasan K. , Reddy A. S.
• Języki publikacji: EN

Abstrakty

EN

Insertion grammars have been introduced in [1] and their computational power has been studied in several places. In [7] it is proved that insertion grammars with weight at least 7 can characterize recursively enumerable languages (modulo a weak coding and an inverse morphism), and the question was formulated whether or not this result can be improved. In this paper, we come up with a positive answer to this question, by decreasing the weight of the insertion grammar used to 5. We also give a characterization of recursively enumerable languages in terms of right quotients of insertion languages.

Słowa kluczowe

EN

insertion grammars; contextual grammars; recursively enumerable languages; Penttonen normal form; kuroda normal form

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 317--324
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Mutyam M.

• International Institute of Information Technology, Hyderabad, Gachibowli, Hyderabad-19, India

autor

Krithivasan K.

• Department of Computer Science and Engineering Indian Institute of Technology Madras, Chennai-36, India

autor

Reddy A. S.

• Department of Computer Science New York University, NY, USA

Bibliografia

• [1] B.S. Galiukschov, Semicontextual Grammars (in Russian). Mat. logica i mat. ling., Kalinin University, 1981, 38–50.
• [2] A.K. Joshi, L.S. Levy, and M. Takahashi, Tree Adjunct Grammar. J. Computer Systems Sci., 19 (1975), 136–163.
• [3] L. Kari, On Insertion and Deletion in Formal Languages. PhD Thesis, Turku University, 1991.
• [4] 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, Proc. of 3rd DIMACS Workshop on DNA Based Computing, Philadelphia, 1997, 318–333.
• [5] A. Lindenmayer, Developmental Algorithms for Multicellular Organisms: A Survey of L Systems. Journal of Theoretical Biology, 54 (1975), 3–22
• [6] S. Marcus, Contextual Grammars, Rev. Roum. Math. Pures Appl., 14 (1969), 1525–1534.
• [7] C. Mart´ın-Vide, Gh. Păun, and A. Salomaa, A Characterization of Recursively Enumerable Languages by Means of Insertion Grammars. Theoretical Computer Science, 205, 1-2 (1998), 195–205.
• [8] Gh. Păun, Marcus Contextual Grammars. Kluwer Academic Publishers, 1997.
• [9] Gh. Păun, G. Rozenberg, and A. Salomaa, DNA Computing. New Computing Paradigms. Springer-Verlag, Berlin, 1998.
• [10] G. Rozenberg and A. Salomaa, Eds., Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.