Universal insertion grammars of size two

DOI10.1016/J.TCS.2020.09.002zbMATH Open1460.68047OpenAlexW3084341121MaRDI QIDQ2004002FDOQ2004002

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

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

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)

Cites Work

• Context-free insertion-deletion systems
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Normal forms for phrase-structure grammars
• Title not available (Why is that?)
• Graph-controlled insertion-deletion systems
• Title not available (Why is that?)
• Recent developments on insertion-deletion systems
• Matrix insertion-deletion systems
• Insertion languages
• Restarting automata
• Marcus contextual grammars
• On the computational power of insertion-deletion systems
• On minimal context-free insertion-deletion systems
• Insertion-Deletion Systems with One-Sided Contexts
• New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality
• Contextual insertions/deletions and computability
• On the weight of universal insertion grammars
• Universal matrix insertion grammars with small size
• Title not available (Why is that?)
• Title not available (Why is that?)
• Morphic characterizations of language families in terms of insertion systems and star languages
• Universality of graph-controlled leftist insertion-deletion systems with two states
• On the decidability of accessibility problems (extended abstract)

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
• Title not available (Why is that?)
• \(\mathcal{L}\)-reduction computation revisited
• Title not available (Why is that?)

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)