SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED
Lila Kari, Shinnosuke Seki · International Journal of Foundations of Computer Science · 2011
A general framework of parallel insertion and deletion based on p-schemata is proposed. A p-schema is a set of tuples of words. When being used for parallel insertion of a language into a word, an element of p-schema specifies how to split the word into factors between which the language to be inserted. As its inverse operation, parallel deletion based on the p-schema is defined. Several algebraic properties of these operations such as closure properties of language classes under them are proved. The main contribution of this paper is to propose algorithms to solve language equations involving p-schema-based insertions or deletions based on syntactic congruence. These algorithms not only decide whether a given equation has a solution but construct the set of all of its maximal or minimal solutions. The algorithms are extensible so as to solve some multiple-variables equations and inequalities. Related undecidability results are also presented.