Skip to Main content Skip to Navigation

# Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems

Abstract : We consider graph-controlled insertion-deletion systems and prove that the systems with sizes (i) (3; 1, 1, 1; 1, 0, 1), (ii) $(3;1,1,1;1,1,0)$ and (iii) (2; 2, 0, 0; 1, 1, 1) are computationally complete. Moreover, graph-controlled insertion-deletion systems simulate linear languages with sizes (2; 2, 0, 1, 1, 0, 0), (2; 2, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), or (3; 1, 1, 0; 1, 0, 0). Simulations of metalinear languages are also studied. The parameters in the size $(k;n,i',i'';m,j',j'')$ of a graph-controlled insertion-deletion system denote (from left to right) the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; a similar list of three parameters concerning deletion follows.
Keywords :
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [20 references]

https://hal.inria.fr/hal-01633956
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, November 13, 2017 - 3:32:53 PM
Last modification on : Wednesday, December 6, 2017 - 11:42:02 AM
Long-term archiving on: : Wednesday, February 14, 2018 - 3:17:47 PM

### File

416473_1_En_9_Chapter.pdf
Files produced by the author(s)

### Licence

Distributed under a Creative Commons Attribution 4.0 International License

### Citation

Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman. Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.111-125, ⟨10.1007/978-3-319-41114-9_9⟩. ⟨hal-01633956⟩

Record views

Files downloads