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

DOI10.1142/S0129054108006005zbMath1156.68033MaRDI QIDQ3526540

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

Publication date: 25 September 2008

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

zbMATH Keywords

context-free languagesinsertion-deletion operations

Mathematics Subject Classification ID

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

Related Items (10)

\(\mathcal{L}\)-reduction computation revisited ⋮ Outfix-guided insertion ⋮ Single semi-contextual insertion-deletion systems ⋮ Unnamed Item ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ 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 OF LANGUAGE FAMILIES IN TERMS OF INSERTION SYSTEMS AND STAR LANGUAGES ⋮ Outfix-Guided Insertion ⋮ On the overlap assembly of strings and languages

Cites Work

• Unnamed Item
• Contextual insertions/deletions and computability
• A homomorphic characterization of recursively enumerable languages
• On the impossibility of the homomorphic characterization of context- sensitive languages
• Reversal-bounded multipushdown machines
• Characterizations of recursively enumerable languages by means of insertion grammars
• On the computational power of insertion-deletion systems
• Context-free insertion-deletion systems

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