ON LANGUAGE EQUATIONS WITH INVERTIBLE OPERATIONS

The paper studies language equations of the type X lozenge L = R and L lozenge Y = R, where L and R are given languages and lozenge is an in vertible binary word (language) operation. For most of the considered insertion and deletion operations, the existence of both a solution an d a singleton solution to these equations proves to be decidable for g iven regular L and R. In case L is a context-free language and R is a regular one, the existence of a solution is generally undecidable. The results can be extended to more complex linear equations, systems of linear equations as well as for equations of higher degree.