Universal matrix insertion grammars with small size

DOI10.1007/978-3-319-58187-3_14MaRDI QIDQ2400963zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, Sergey Verlan

Publication date 31 August 2017

Full work available at URL https://doi.org/10.1007/978-3-319-58187-3_14

zbMATH Keywords

homomorphisminsertion grammarsmatrix insertion grammarsrecursively enumerable setsregular intersection and quotient

Mathematics Subject Classification ID

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

Recommendations

• Universal insertion grammars of size two
• On the weight of universal insertion grammars
• On matrix ins-del systems of small sum-norm
• scientific article; zbMATH DE number 2182439
• Matrix insertion-deletion systems

Cited in

(11)

• Universal insertion grammars of size two
• Prescribed teams of rules working on several objects
• Modeling of RNA secondary structures using two-way quantum finite automata
• On Szilard languages of InsDel systems
• Decidability questions for insertion systems and related models
• Regulated insertion-deletion systems
• On the generative capacity of matrix insertion-deletion systems of small sum-norm
• Single semi-contextual insertion-deletion systems
• On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2
• Parsimonious computational completeness
• On the weight of universal insertion grammars

This page was built for publication: Universal matrix insertion grammars with small size

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