Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01633956
Contributor : Hal Ifip <>
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

Identifiers

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⟩

Share

Metrics

Record views

210

Files downloads

166