Deletion along trajectories

We describe a new way to model deletion operations on formal languages, called deletion along trajectories. We examine its closure properties, which differ from those of shuffle on trajectories, previously introduced by Mateescu et al. In particular, we define classes of non-regular sets of trajectories such that the associated deletion operation preserves regularity. Our results give uniform proofs of closure properties of the regular languages for several deletion operations.

We also show that deletion along trajectories serves as an inverse to shuffle on trajectories. This leads to results on the decidability of certain language equations, including those of the form LTX=R, where L,R are regular languages and X is unknown.