Descriptional complexity of graph-controlled insertion-deletion systems

DOI10.1007/978-3-319-41114-9_9MaRDI QIDQ2829975zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

Publication date 9 November 2016

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01633956/file/416473_1_En_9_Chapter.pdf

zbMATH Keywords

computational completenessinsertion-deletion systemsdescriptional complexity measuresgraph-controlled systems

Mathematics Subject Classification ID

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

Recommendations

• Graph-controlled insertion-deletion systems
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• On path-controlled insertion-deletion systems
• Computational completeness of path-structured graph-controlled insertion-deletion systems
• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes

Cites work

• scientific article; zbMATH DE number 21368 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• About one-sided one-symbol insertion-deletion P systems
• Computational power of insertion-deletion (P) systems with rules of size two
• Context-free insertion-deletion systems
• Contextual insertions/deletions and computability
• Finite turns and the regular closure of linear context-free languages
• Insertion languages
• Matrix insertion-deletion systems
• On the computational power of insertion-deletion systems
• P systems with minimal insertion and deletion
• Recent developments on insertion-deletion systems
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Universality of graph-controlled leftist insertion-deletion systems with two states

Cited in

(11)

• On path-controlled insertion-deletion systems
• Computational completeness of path-structured graph-controlled insertion-deletion systems
• Universality of graph-controlled leftist insertion-deletion systems with two states
• Computational completeness of simple semi-conditional insertion-deletion systems
• Generative power of matrix insertion-deletion systems with context-free insertion or deletion
• Graph-controlled insertion-deletion systems
• scientific article; zbMATH DE number 1953225 (Why is no real title available?)
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Graph-controlled insertion-deletion systems generating language classes beyond linearity
• On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes

This page was built for publication: Descriptional complexity of graph-controlled insertion-deletion systems

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