Contextual insertions/deletions and computability

DOI10.1006/INCO.1996.0091zbMATH Open0872.68038OpenAlexW2075622371MaRDI QIDQ675056FDOQ675056

Authors: Lila Kari, Gabriel Thierrin 

Publication date: 13 October 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1996.0091

Recommendations

• Computational completeness of simple semi-conditional insertion-deletion systems
• Context-free insertion-deletion systems
• Universality and computational completeness of controlled leftist insertion-deletion systems
• On the computational power of insertion-deletion systems
• scientific article; zbMATH DE number 1953225
• Insertion-deletion with substitutions. II: About the role of one-sided context
• Random context and semi-conditional insertion-deletion systems
• Insertion and deletion closure of languages
• Decidability questions for insertion systems and related models
• On minimal context-free insertion-deletion systems

zbMATH Keywords

Turing machinedeletionscontextual insertions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (56)

• Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)
• Evaluating space measures in P systems
• When Stars Control a Grammar's Work
• On decision problems concerning contextual insertions and deletions
• On path-controlled insertion-deletion systems
• Cut-and-paste languages
• Single semi-contextual insertion-deletion systems
• On Szilard languages of InsDel systems
• Computational power of intramolecular gene assembly
• Computational power of insertion-deletion (P) systems with rules of size two
• P systems with minimal insertion and deletion
• Computational completeness of path-structured graph-controlled insertion-deletion systems
• Title not available (Why is that?)
• Experimental efficiency of programmed mutagenesis
• Matrix insertion-deletion systems
• Using DNA to solve the bounded Post correspondence problem
• Universality of graph-controlled leftist insertion-deletion systems with two states
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• On the ambiguity of insertion systems
• Generative power of matrix insertion-deletion systems with context-free insertion or deletion
• On the weight of universal insertion grammars
• Investigations on the power of matrix insertion-deletion systems with small sizes
• Parikh images of matrix ins-del systems
• Universal insertion grammars of size two
• Outfix-guided insertion (extended abstract)
• On succinct description of certain context-free languages by ins-del and matrix ins-del systems
• On the generative capacity of matrix insertion-deletion systems of small sum-norm
• Context-free insertion-deletion systems
• Circular Post machines and P systems with exo-insertion and deletion
• Characterizations of recursively enumerable languages by means of insertion grammars
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2
• Hybrid networks of evolutionary processors are computationally complete
• Parallel contextual array insertion-deletion P systems and array rewriting P systems with pure 2D context-free rules
• Context insertions
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Possibilities of constructing two dimensional pictures in DNA computing: Part I
• Random context and semi-conditional insertion-deletion systems
• Nondeterministic state complexity of site-directed deletion
• Schema for parallel insertion and deletion: revisited
• Transposition based contextual insertion on linear DNA strands with deletion precedence
• Parallel contextual array insertion deletion P systems and tabled matrix grammars
• Bounded hairpin completion
• Site-directed insertion: language equations and decision problems
• Outfix-guided insertion
• The nondeterministic state complexity of the site-directed deletion language operation
• Title not available (Why is that?)
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Bounded Hairpin Completion
• DNA computing, insertion of words and left-symmetric algebras
• Maximally parallel contextual string rewriting
• DNA computing: Arrival of biological mathematics
• Algorithmic applications of XPCR
• Descriptional complexity of graph-controlled insertion-deletion systems
• On bonded sequential and parallel insertion systems

This page was built for publication: Contextual insertions/deletions and computability

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