On the Power of Star-Controlled Insertion-Deletion Systems

Graph-controlled insertion-deletion (GCID) systems are regulated extensions of insertion-deletion systems. Such a system has several components and each component contains a set of insertion-deletion rules. The components are the vertices of a directed control graph whose arcs describe how strings can move between components. A rule is applied to a string in a component and the resultant string is 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. In this paper, we impose the restriction in the structure of the underlying graph to be a star structure where there is a central, control component that acts like a master and transmits a string (after applying one of its rules) to one of the components specified in the (applied) rule. A component receiving the string can process the obtained string with any applicable rule available in it, and sends back the resultant string only to the central component. Both the central and the other components cannot hold back the resultant string in the same component. With these restrictions, we generate some non-linear languages using star-controlled insertion-deletion system and further obtain computational completeness for some descriptional complexity measures. The obtained results can be applied to membrane computing, since the star structure is a tree structure also, and the membrane structure adheres to it.