On the computational power of insertion-deletion systems
From MaRDI portal
Publication:1426832
DOI10.1023/B:NACO.0000006769.27984.23zbMath1074.68021OpenAlexW3013369976MaRDI QIDQ1426832
Takashi Yokomori, Akihiro Takahara
Publication date: 15 March 2004
Published in: Natural Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/b:naco.0000006769.27984.23
Related Items (27)
On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ Insertion-deletion systems with substitutions I ⋮ Parsimonious computational completeness ⋮ Computational completeness of path-structured graph-controlled insertion-deletion systems ⋮ Outfix-guided insertion ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ 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 ⋮ When Stars Control a Grammar's Work ⋮ On Succinct Description of Certain Context-Free Languages by Ins-Del and Matrix Ins-Del Systems ⋮ State Complexity of Insertion ⋮ REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS ⋮ Unnamed Item ⋮ On path-controlled insertion-deletion systems ⋮ On the weight of universal insertion grammars ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Universal insertion grammars of size two ⋮ Computational power of insertion-deletion (P) systems with rules of size two ⋮ Matrix insertion-deletion systems ⋮ Outfix-Guided Insertion ⋮ On the overlap assembly of strings and languages ⋮ Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems ⋮ Insertion-deletion systems with substitutions. I
This page was built for publication: On the computational power of insertion-deletion systems
