On the generative capacity of matrix insertion-deletion systems of small sum-norm

DOI10.1007/S11047-021-09866-YMaRDI QIDQ6095512zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

Publication date 8 September 2023

Published in Natural Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s11047-021-09866-y

zbMATH Keywords

computational completenessdescriptional complexityinsertion-deletion systemslinear languagesmatrix controlregular closure

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• On matrix ins-del systems of small sum-norm
• Investigations on the power of matrix insertion-deletion systems with small sizes
• Generative power of matrix insertion-deletion systems with context-free insertion or deletion
• Parikh images of matrix ins-del systems
• Matrix insertion-deletion systems

Cites work

• Adding matrix control: insertion-deletion systems with substitutions. III
• Computational completeness of path-structured graph-controlled insertion-deletion systems
• Computational completeness of simple semi-conditional insertion-deletion systems
• Computational power of insertion-deletion (P) systems with rules of size two
• Context-free insertion-deletion systems
• Contextual insertions/deletions and computability
• DNA computing: Arrival of biological mathematics
• Graph-controlled insertion-deletion systems
• Graph-controlled insertion-deletion systems generating language classes beyond linearity
• scientific article; zbMATH DE number 4160148 (Why is no real title available?)
• scientific article; zbMATH DE number 21368 (Why is no real title available?)
• scientific article; zbMATH DE number 193524 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• Insertion languages
• Investigations on the power of matrix insertion-deletion systems with small sizes
• Matrix insertion-deletion systems
• Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
• On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
• On matrix ins-del systems of small sum-norm
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
• P systems with minimal insertion and deletion
• Parikh images of matrix ins-del systems
• Properties of language classes between linear and context-free
• Random context and semi-conditional insertion-deletion systems
• Recent developments on insertion-deletion systems
• Universal insertion grammars of size two
• Universal matrix insertion grammars with small size
• Universality and computational completeness of controlled leftist insertion-deletion systems

Cited in

(7)

• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
• Investigations on the power of matrix insertion-deletion systems with small sizes
• When Stars Control a Grammar's Work
• Space separating special Geffert normal form for succinct representation of star-controlled insertion-deletion systems
• Star-controlled insertion-deletion systems describing regular closure of linear languages
• Succinct star-controlled insertion-deletion systems using space separating normal forms
• On time-varying insertion-deletion systems

This page was built for publication: On the generative capacity of matrix insertion-deletion systems of small sum-norm

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