Contextual insertions/deletions and computability
From MaRDI portal
Publication:675056
DOI10.1006/inco.1996.0091zbMath0872.68038OpenAlexW2075622371MaRDI QIDQ675056
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
Related Items
On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ Transposition based contextual insertion on linear DNA strands with deletion precedence ⋮ Circular Post Machines and P Systems with Exo-insertion and Deletion ⋮ SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED ⋮ ON THE AMBIGUITY OF INSERTION SYSTEMS ⋮ DNA computing: Arrival of biological mathematics ⋮ Nondeterministic state complexity of site-directed deletion ⋮ Computational completeness of path-structured graph-controlled insertion-deletion systems ⋮ Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States ⋮ Outfix-guided insertion ⋮ P systems with minimal insertion and deletion ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ On the generative capacity of matrix insertion-deletion systems of small sum-norm ⋮ Single semi-contextual insertion-deletion systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2 ⋮ Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1) ⋮ Unnamed Item ⋮ The nondeterministic state complexity of the site-directed deletion language operation ⋮ Evaluating space measures in P systems ⋮ When Stars Control a Grammar's Work ⋮ On Succinct Description of Certain Context-Free Languages by Ins-Del and Matrix Ins-Del Systems ⋮ REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS ⋮ On path-controlled insertion-deletion systems ⋮ On the weight of universal insertion grammars ⋮ Parikh Images of Matrix Ins-Del Systems ⋮ Further Results on Insertion-Deletion Systems with One-Sided Contexts ⋮ Regulated RNA rewriting: Modelling RNA editing with guided insertion ⋮ Context Insertions ⋮ Possibilities of constructing two dimensional pictures in DNA computing: Part I ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Universal insertion grammars of size two ⋮ Context-free insertion-deletion systems ⋮ Experimental efficiency of programmed mutagenesis ⋮ Bounded hairpin completion ⋮ Algorithmic applications of XPCR ⋮ Computational power of insertion-deletion (P) systems with rules of size two ⋮ Hybrid networks of evolutionary processors are computationally complete ⋮ Matrix insertion-deletion systems ⋮ COMPUTATIONAL POWER OF INTRAMOLECULAR GENE ASSEMBLY ⋮ Bounded Hairpin Completion ⋮ Outfix-Guided Insertion ⋮ Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion ⋮ Parallel contextual array insertion deletion P systems and tabled matrix grammars ⋮ On bonded sequential and parallel insertion systems ⋮ Characterizations of recursively enumerable languages by means of insertion grammars ⋮ Maximally Parallel Contextual String Rewriting ⋮ Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems ⋮ Using DNA to solve the bounded Post correspondence problem ⋮ Site-directed insertion: language equations and decision problems