Characterizations of recursively enumerable languages by means of insertion grammars

DOI10.1016/S0304-3975(97)00079-0zbMath0913.68126OpenAlexW2038631884MaRDI QIDQ1275078

Arto Salomaa, Gheorghe Păun, Carlos Martín-Vide

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00079-0

zbMATH Keywords

insertion grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (17)

Circular Post Machines and P Systems with Exo-insertion and Deletion ⋮ P systems with minimal insertion and deletion ⋮ Unnamed Item ⋮ REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS ⋮ On the weight of universal insertion grammars ⋮ Further Results on Insertion-Deletion Systems with One-Sided Contexts ⋮ Regulated RNA rewriting: Modelling RNA editing with guided insertion ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Context-free insertion-deletion systems ⋮ Morphic characterizations of languages in Chomsky hierarchy with insertion and locality ⋮ Theoretical and computational properties of transpositions ⋮ Computational power of insertion-deletion (P) systems with rules of size two ⋮ Hybrid networks of evolutionary processors are computationally complete ⋮ 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 ⋮ Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion ⋮ Derivation languages and descriptional complexity measures of restricted flat splicing systems

Cites Work

• Contextual insertions/deletions and computability
• Tree adjunct grammars
• On representing recursively enumerable languages by internal contextual languages
• Pure grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Characterizations of recursively enumerable languages by means of insertion grammars