Watson-Crick Linear Grammars

Autor:	Mohd Izzuddin Mohd Tamrin, Azeddine Messikh, Sherzod Turaev, Nurul Liyana Mohamad Zulkufli
Rok vydání:	2019
Předmět:	Tree-adjoining grammar Indexed language Computer science Programming language Formal language Abstract family of languages Context-sensitive grammar Indexed grammar Context-free grammar Phrase structure grammar computer.software_genre computer
Zdroj:	Proceedings of the International Conference on Data Engineering 2015 (DaEng-2015) ISBN: 9789811317972 DaEng
DOI:	10.1007/978-981-13-1799-6_42
Popis:	In this paper, we define Watson-Crick linear grammars extending Watson-Crick regular grammars Subramanian et al. (CCSEIT’12 proceedings of the second international conference on computer science, science, engineering and information technology 151–156, 2012, [9]) with linear rules, and study their generative power. We show that Watson-Crick linear grammars can generate some context-sensitive languages. Moreover, we establish that the family of Watson-Crick regular languages proper subset of the family of Watson-Crick linear languages but it is not comparable with the family of linear languages.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::56fb901d058e0ff356ad25802c16e106 https://doi.org/10.1007/978-981-13-1799-6_42 Zobrazit plný text záznamu