We propose a general framework for parallel insertion/deletion operations based on p-schemata. 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 a p-schema specifies how to split the given word into factors between which the insertion of the language will take place. Parallel deletion based on a p-schema is defined as an "inverse" operation of parallel insertion based on the p-schema. Several well-known language operations are particular cases of p-schema-based insertions or deletions: catenation, Kleene star, reverse catenation, sequential insertion, parallel insertion, insertion next to a given letter, contextual insertion, right and left quotient, sequential deletion, parallel deletion. Additional operations that can be defined using p-schemata include contextual parallel insertion, as well as parallel insertion (deletion) of exactly n words, at most n words, an arbitrary number of words. We also consider the decidability and undecidability of existence of solutions of language equations involving p-schema-based parallel insertion/deletion.
['Lila Kari', 'Shinnosuke Seki']
Schema for parallel insertion and deletion