Universal insertion grammars of size two
From MaRDI portal
Publication:2004002
DOI10.1016/J.TCS.2020.09.002zbMath1460.68047OpenAlexW3084341121MaRDI QIDQ2004002
Lakshmanan Kuppusamy, Sergey Verlan, Henning Fernau
Publication date: 13 October 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.09.002
Grammars and rewriting systems (68Q42) Recursively (computably) enumerable sets and degrees (03D25) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)
Related Items (5)
Parsimonious computational completeness ⋮ \(\mathcal{L}\)-reduction computation revisited ⋮ On the generative capacity of matrix insertion-deletion systems of small sum-norm ⋮ Unnamed Item ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recent developments on insertion-deletion systems
- Contextual insertions/deletions and computability
- Matrix insertion-deletion systems
- Insertion languages
- On the weight of universal insertion grammars
- On the computational power of insertion-deletion systems
- Marcus contextual grammars
- Context-free insertion-deletion systems
- Universal matrix insertion grammars with small size
- Regulated RNA rewriting: Modelling RNA editing with guided insertion
- Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States
- MORPHIC CHARACTERIZATIONS OF LANGUAGE FAMILIES IN TERMS OF INSERTION SYSTEMS AND STAR LANGUAGES
- On the decidability of accessibility problems (extended abstract)
- Insertion-Deletion Systems with One-Sided Contexts
- New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality
- Normal forms for phrase-structure grammars
- Restarting automata
This page was built for publication: Universal insertion grammars of size two
