Descriptional complexity of graph-controlled insertion-deletion systems

DOI10.1007/978-3-319-41114-9_9zbMATH Open1410.68184OpenAlexW2491357875MaRDI QIDQ2829975FDOQ2829975

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

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

zbMATH Keywords

computational completenessinsertion-deletion systemsdescriptional complexity measuresgraph-controlled systems

Mathematics Subject Classification ID

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

Cites Work

• Context-free insertion-deletion systems
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Title not available (Why is that?)
• Computational power of insertion-deletion (P) systems with rules of size two
• P systems with minimal insertion and deletion
• Recent developments on insertion-deletion systems
• Matrix insertion-deletion systems
• Insertion languages
• Title not available (Why is that?)
• On the computational power of insertion-deletion systems
• Contextual insertions/deletions and computability
• Title not available (Why is that?)
• Finite turns and the regular closure of linear context-free languages
• About one-sided one-symbol insertion-deletion P systems
• 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
• Title not available (Why is that?)
• 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)