Universal insertion grammars of size two

DOI10.1016/J.TCS.2020.09.002MaRDI QIDQ2004002zbMATH OpenOpenAlexFDO

Authors Sergey Verlan, Henning Fernau, Lakshmanan Kuppusamy

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

zbMATH Keywords

recursively enumerable setshomomorphic representationinsertion grammarsinsertion systems

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Recursively (computably) enumerable sets and degrees (03D25) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Recommendations

• On the weight of universal insertion grammars
• Universal matrix insertion grammars with small size
• Characterizations of recursively enumerable languages by means of insertion grammars
• scientific article; zbMATH DE number 2182439
• scientific article; zbMATH DE number 1342113

Cites work

• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 1342113 (Why is no real title available?)
• scientific article; zbMATH DE number 2182439 (Why is no real title available?)
• scientific article; zbMATH DE number 3307580 (Why is no real title available?)
• Context-free insertion-deletion systems
• Contextual insertions/deletions and computability
• Graph-controlled insertion-deletion systems
• Insertion languages
• Insertion-Deletion Systems with One-Sided Contexts
• Marcus contextual grammars
• Matrix insertion-deletion systems
• 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
• Normal forms for phrase-structure grammars
• On minimal context-free insertion-deletion systems
• On the computational power of insertion-deletion systems
• On the decidability of accessibility problems (extended abstract)
• On the weight of universal insertion grammars
• Recent developments on insertion-deletion systems
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Restarting automata
• Universal matrix insertion grammars with small size
• Universality of graph-controlled leftist insertion-deletion systems with two states

Cited in

(8)

• Parsimonious computational completeness
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• On the weight of universal insertion grammars
• On the generative capacity of matrix insertion-deletion systems of small sum-norm
• Universal matrix insertion grammars with small size
• scientific article; zbMATH DE number 2182439 (Why is no real title available?)
• \(\mathcal{L}\)-reduction computation revisited
• scientific article; zbMATH DE number 7584595 (Why is no real title available?)

This page was built for publication: Universal insertion grammars of size two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004002)