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.
Type de document :
Communication dans un congrès
Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.111-125, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_9〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01633956
Contributeur : Hal Ifip <>
Soumis le : lundi 13 novembre 2017 - 15:32:53
Dernière modification le : mercredi 6 décembre 2017 - 11:42:02
Document(s) archivé(s) le : mercredi 14 février 2018 - 15:17:47

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman. Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems. Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.111-125, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_9〉. 〈hal-01633956〉

Partager

Métriques

Consultations de la notice

32