A graph-controlled insertion-deletion (GCID) system has several components and each component contains some insertion-deletion rules. A transition is performed by any applicable rule in the current component on a string and the resultant string is then moved to the target component specified in the rule. The language of the system is the set of all terminal strings collected in the final component. When resources are very limited (especially, when deletion is demanded to be context-free and insertion to be one-sided only), then GCID systems are not known to describe the class of recursively enumerable languages. Hence, it becomes interesting to explore the descriptional complexity of such GCID systems of small sizes with respect to language classes below RE and even below CF. To this end, we consider so-called closure classes of linear languages defined over the operations concatenation, Kleene star and union. We show that whenever GCID systems (with certain syntactical restrictions) describe all linear languages (LIN) with t components, we can extend this to GCID systems with just one more component to describe, for instance, the concatenation of two languages from the language family that can be described as the Kleene closure of linear languages. With further addition of one more component, we can extend the construction to GCID systems that describe the regular closure of LIN.
Accepté le :
DOI : 10.1051/ita/2018005
Mots-clés : Insertion-deletion systems, graph-controlled systems, descriptional complexity measures, regular closure of linear languages
@article{ITA_2018__52_1_1_0,
author = {Fernau, Henning and Kuppusamy, Lakshmanan and Raman, Indhumathi},
title = {On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {1--21},
publisher = {EDP-Sciences},
volume = {52},
number = {1},
year = {2018},
doi = {10.1051/ita/2018005},
mrnumber = {3843152},
zbl = {1400.68102},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2018005/}
}
TY - JOUR AU - Fernau, Henning AU - Kuppusamy, Lakshmanan AU - Raman, Indhumathi TI - On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 1 EP - 21 VL - 52 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2018005/ DO - 10.1051/ita/2018005 LA - en ID - ITA_2018__52_1_1_0 ER -
%0 Journal Article %A Fernau, Henning %A Kuppusamy, Lakshmanan %A Raman, Indhumathi %T On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 1-21 %V 52 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2018005/ %R 10.1051/ita/2018005 %G en %F ITA_2018__52_1_1_0
Fernau, Henning; Kuppusamy, Lakshmanan; Raman, Indhumathi. On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 1, pp. 1-21. doi : 10.1051/ita/2018005. http://www.numdam.org/articles/10.1051/ita/2018005/
[1] , and , Descriptional complexity of graph-controlled insertion-deletion systems, in 18th International Conference on Descriptional Complexity of Formal Systems (DCFS), edited by , , . Vol. 9777 of LNCS. Springer (2016) 111–125. | DOI | MR
[2] , and , Computational completeness of path-structured graph-controlled insertion-deletion systems, in 22nd International Conference on Implementation and Application of Automata CIAA, edited by , Vol. 10329 of LNCS. Springer (2017) 89–100. | DOI | MR | Zbl
[3] , and , Graph-controlled insertion-deletion systems generating language classes beyond linearity, in 19th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems DCFS, edited by , . Vol. 316 of LNCS. Springer (2017) 128–139. | DOI | MR | Zbl
[4] , and , On path-controlled insertion-deletion systems. Submitted to Acta Inform. (2017). | MR | Zbl
[5] , and , On the computational completeness of graph-controlled insertion-deletion systems with binary sizes. Theor. Comput. Sci. 682 (2017) 100–121. Special Issue on Languages and Combinatorics in Theory and Nature. | DOI | MR | Zbl
[6] , and On the generative power of graph-controlled insertion-deletion systems with small sizes. J. Autom. Lang. Comb. 22 (2017) 61–92. | MR | Zbl
[7] , and , Properties of language classes between linear and context-free. Submitted to J. Autom. Lang. Comb. (2017). | MR
[8] , , and , Graph-controlled insertion-deletion systems, in Proceedings 12th Annual Workshop on Descriptional Complexity of Formal Systems (DCFS), edited by and . Vol. 31 of EPTCS (2010) 88–98. | Zbl
[9] , Semicontextual grammars (in Russian). Mat. logica i mat. ling., Kalinin Univ. (1981) 38–50.
[10] and , Pumping lemmas for linear and nonlinear context-free languages. Acta Univ. Sapientiae Inform. 2 (2010) 194–209. | Zbl
[11] and , Finite turns and the regular closure of linear context-free languages. Discret. Appl. Math. 155 (2007) 2152–2164. | DOI | MR | Zbl
[12] , and , DNA Computing: New Computing Paradigms. Springer (1998). | DOI | MR | Zbl
[13] Recent developments on insertion-deletion systems. Comput. Sci. J. Mold. 18 (2010) 210–245. | MR | Zbl
Cité par Sources :
