Title: Language Equations with Trajectory-Based Operations 

Speaker: Kai Salomaa
School of Computing, Queen's University
Kingston, Ontario, Canada 

Date: Friday Sept 23, 2005
Time 11-12 Venue: Room 3464 , HKUST   


Abstract 
We consider decidability of existence of solutions
for language equations involving trajectory-based
operations. A trajectory is a word over {0,1}. Each trajectory t
having m 0's and n 1's defines a particular way in which two
words of length m and n are shuffled. The operation is extended
in the natural way for languages and sets of trajectories.
Deletion along a trajectory is defined in a similar way.
Operations defined by regular sets of trajectories generalize
the operations of
catenation, insertion, shuffle, quotient, sequential and
scattered deletion, as well as many others.

We discuss both positive and negative decidability
results. The results are constructive in the sense that
if a solution exists, it can be effectively represented.
Many of the results can be extended for systems of equations.

Important questions remain open even for regular sets of trajectories
and equations involving regular languages as constants.
The well known shuffle decomposition problem for regular
languages is a special case that remains open.

This is joint work with Mike Domaratzki.