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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Time-Varying Insertion-Deletion Systems

  • Henning Fernau,
  • Lakshmanan Kuppusamy,
  • Indhumathi Raman

摘要

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.