On language equations with invertible operations

AbstractThe paper studies language equations of the type X ◊ L = R and L ◊ Y = R, where L and R are given languages and ◊ is an invertible binary word (language) operation. For most of the considered insertion and deletion operations, the existence of both a solution and a singleton solution to these equations proves to be decidable for given 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