On Time-Varying Insertion-Deletion Systems
摘要
Graph-controlled insertion-deletion (GCID) systems are regulated extensions of insertion-deletion systems. In 2022, Alhazov et al. introduced time-varying systems as a restriction of GCID systems; in these systems, the components are cyclically ordered. A rule is applied to a string in a component and the resultant string moves to the next component as specified by this order. The language of the system is the set of all terminal strings collected in a distinguished component that is both the initial and the final one. With this restriction, we obtain several new computational completeness results for some typical descriptional complexity measures well-studied in the area of GCID systems.