Decidability of trajectory-based equations
We consider the decidability of existence of solutions to language equations involving the operations of shuffle and deletion along trajectories. These operations generalize the operations of catenation, insertion, shuffle, quotient, sequential and scattered deletion, as well as many others. Our results are constructive in the sense that if a solution exists, it can be effectively represented. We show both positive and negative decidability results. We also briefly consider systems of language equations. (c) 2005 Elsevier B.V. All rights reserved.
language equations deletion along trajectories shuffle on trajectories shuffle decompositions