Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems - Descriptional Complexity of Formal Systems (DCFS 2016)
Conference Papers Year : 2016

Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems

Henning Fernau
  • Function : Author
  • PersonId : 857693
Lakshmanan Kuppusamy
  • Function : Author
  • PersonId : 917459
Indhumathi Raman
  • Function : Author
  • PersonId : 1022737

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.
Fichier principal
Vignette du fichier
416473_1_En_9_Chapter.pdf (468.98 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01633956 , version 1 (13-11-2017)

Licence

Identifiers

Cite

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⟩
123 View
128 Download

Altmetric

Share

More