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

DOI10.1142/S0129054108006005MaRDI QIDQ3526540zbMATH OpenFDO

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)

Full work available at URL https://doi.org/10.1142/S0129054108006005

zbMATH Keywords

context-free languagesinsertion-deletion operations

Mathematics Subject Classification ID

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

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

Cites work

• A homomorphic characterization of recursively enumerable languages
• Characterizations of recursively enumerable languages by means of insertion grammars
• Context-free insertion-deletion systems
• Contextual insertions/deletions and computability
• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• On the computational power of insertion-deletion systems
• On the impossibility of the homomorphic characterization of context- sensitive languages
• Reversal-bounded multipushdown machines

Cited in

(15)

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

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)