REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS

DOI10.1142/S0129054108006005zbMATH Open1156.68033MaRDI QIDQ3526540FDOQ3526540

Authors: Gheorghe Păun, Mario J. Pérez-Jiménez, Takashi Yokomori 

Publication date: 25 September 2008

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Recommendations

• Morphic characterizations of languages in Chomsky hierarchy with insertion and locality
• New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality
• Morphic Characterizations in Terms of Insertion Systems with a Context of Length One
• Morphic characterizations of language families in terms of insertion systems and star languages
• scientific article; zbMATH DE number 1342113

zbMATH Keywords

context-free languagesinsertion-deletion operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Context-free insertion-deletion systems
• Reversal-bounded multipushdown machines
• Title not available (Why is that?)
• Characterizations of recursively enumerable languages by means of insertion grammars
• On the computational power of insertion-deletion systems
• Contextual insertions/deletions and computability
• A homomorphic characterization of recursively enumerable languages
• On the impossibility of the homomorphic characterization of context- sensitive languages

Cited In (14)

• Single semi-contextual insertion-deletion systems
• Morphic characterizations of language families in terms of insertion systems and star languages
• On Szilard languages of InsDel systems
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• Morphic characterizations of languages in Chomsky hierarchy with insertion and locality
• Outfix-guided insertion (extended abstract)
• Aspects of Molecular Computing
• Title not available (Why is that?)
• Morphic characterizations with insertion systems controlled by a context of length one
• \(\mathcal{L}\)-reduction computation revisited
• Outfix-guided insertion
• On the overlap assembly of strings and languages
• Title not available (Why is that?)
• New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality

This page was built for publication: REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3526540)