On the weight of universal insertion grammars

DOI10.1016/J.TCS.2008.01.037zbMath1145.68028OpenAlexW2082853563MaRDI QIDQ924156

Lila Kari, Petr Sosík

Publication date: 28 May 2008

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.037

zbMATH Keywords

DNA computingformal grammarcontextual insertion

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42)

Related Items (8)

\(\mathcal{L}\)-reduction computation revisited ⋮ Single semi-contextual insertion-deletion systems ⋮ Unnamed Item ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Universal insertion grammars of size two ⋮ Theoretical and computational properties of transpositions ⋮ MORPHIC CHARACTERIZATIONS OF LANGUAGE FAMILIES IN TERMS OF INSERTION SYSTEMS AND STAR LANGUAGES ⋮ On the overlap assembly of strings and languages

Cites Work

• Contextual insertions/deletions and computability
• Characterizations of recursively enumerable languages by means of insertion grammars
• On the computational power of insertion-deletion systems
• Context-free insertion-deletion systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the weight of universal insertion grammars