Voir la notice de l'article provenant de la source Numdam
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
Keywords: Insertion-deletion systems, graph-controlled systems, descriptional complexity measures, regular closure of linear languages
Fernau, Henning 1 ; Kuppusamy, Lakshmanan 1 ; Raman, Indhumathi 1
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :