RAIRO-Theor. Inf. Appl.
Volume 52, Number 1, January–March 2018
|Page(s)||1 - 21|
|Published online||11 July 2018|
On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
Fachbereich 4 – Abteilung Informatikwissenschaften, CIRT, Universität Trier,
2 School of Computer Science and Engineering, VIT, Vellore 632 014, India
3 School of Information Technology and Engineering, VIT, Vellore 632 014, India
* Corresponding author: firstname.lastname@example.org
Accepted: 18 May 2018
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.
Mathematics Subject Classification: 68Q42 / 68Q45 / 03D05
Key words: Insertion-deletion systems / graph-controlled systems / descriptional complexity measures / regular closure of linear languages
© 2018, EDP Sciences
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.