%0 Conference Proceedings
%T Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems
%+ Trier University
%+ VIT University
%A Fernau, Henning
%A Kuppusamy, Lakshmanan
%A Raman, Indhumathi
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS)
%C Bucharest, Romania
%Y Cezar Câmpeanu
%Y Florin Manea
%Y Jeffrey Shallit
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-9777
%P 111-125
%8 2016-07-05
%D 2016
%R 10.1007/978-3-319-41114-9_9
%K Insertion-deletion systems
%K Graph-controlled systems
%K Descriptional complexity measures
%K Computational completeness
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01633956/document
%2 https://inria.hal.science/hal-01633956/file/416473_1_En_9_Chapter.pdf
%L hal-01633956
%U https://inria.hal.science/hal-01633956
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-LNCS-9777
%~ IFIP-WG1-2