Succinct star-controlled insertion-deletion systems using space separating normal forms

DOI10.1007/978-3-031-81202-6_2MaRDI QIDQ6996905zbMATH OpenFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

Publication date 15 April 2025

Full work available at URL https://doi.org/10.1007/978-3-031-81202-6_2

zbMATH Keywords

computational completenessdescriptional complexity measuresgraph-controlinsertion-deletion systemsspace separating SGNFstar structure

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• About one-sided one-symbol insertion-deletion P systems
• Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)
• Contextual insertions/deletions and computability
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Graph-controlled insertion-deletion systems
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 3307580 (Why is no real title available?)
• Insertion-Deletion Systems with One-Sided Contexts
• Matrix insertion-deletion systems
• Normal forms for phrase-structure grammars
• On path-controlled insertion-deletion systems
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• On the generative capacity of matrix insertion-deletion systems of small sum-norm
• Universality and computational completeness of controlled leftist insertion-deletion systems
• When Stars Control a Grammar's Work

Cited in

(1)

• Space separating special Geffert normal form for succinct representation of star-controlled insertion-deletion systems

This page was built for publication: Succinct star-controlled insertion-deletion systems using space separating normal forms

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