Header menu link for other important links
X
Universal insertion grammars of size two
S. Verlan, H. Fernau,
Published in Elsevier B.V.
2020
Volume: 843
   
Pages: 153 - 163
Abstract
In this paper, we show that pure insertion grammars of size 2 (i.e., inserting two symbols in a left and right context, each consisting of two symbols) can characterize all recursively enumerable languages. This is achieved by either applying an inverse morphism and a weak coding, or a left (right) quotient with a regular LOC(2) language, or an intersection with a LOC(2) language and a weak coding. The obtained results improve the descriptional complexity of insertion grammars and complete the picture of known results on insertion-deletion systems that are motivated from the DNA computing area. © 2020 Elsevier B.V.
About the journal
JournalData powered by TypesetTheoretical Computer Science
PublisherData powered by TypesetElsevier B.V.
ISSN03043975