Header menu link for other important links
X
On szilard languages of insdel systems
Published in Institut fur Informatik, Justus-Liebig-Universitat Giessen
2020
Volume: 25
   
Issue: 4
Pages: 321 - 348
Abstract
We study the Szilard languages of InsDel(insertion-deletion) systems. We compare the Szilard languages obtained by these systems with the families of languages in Chomsky hierarchy. We show that although InsDel systems can characterize recursively enumerable languages, there exist some regular languages which cannot be obtained as a Szilard language by any InsDel system. Moreover, InsDel systems of size (1, 1, 1; 1, 1, 1) (i. e., having insertion/deletion rules where one symbol is inserted/deleted in the contexts with one symbol) can obtain context-sensitive languages which are not context-free as Szilard languages. Any regular and context-free language can be obtained as a homomorphic image of Szilard language of InsDel systems of size (1, 1, 1; 1, 1, 0) (i. e., having insertion rules where one symbol is inserted in the contexts with one symbol and deletion rules where one symbol is deleted with one symbol in the left-context) and (3, 1, 1; 1, 1, 1) (i. e., having insertion rules where three symbols are inserted in the contexts with one symbol and deletion rules where one symbol is deleted in the contexts with one symbol) respectively. Also any recursively enumerable language can be obtained as a homomorphic image of the Szilard language of InsDel systems of size (3, 0, 0; 3, 1, 0), (3, 0, 0; 2, 1, 0), (2, 0, 0; 3, 1, 0) and (3, 0, 0; 3, 0, 0). © Institut für Informatik · Justus-Liebig-Universität Giessen.
About the journal
JournalJournal of Automata, Languages and Combinatorics
PublisherInstitut fur Informatik, Justus-Liebig-Universitat Giessen
ISSN1430189X
Open AccessNo