Inhalt des Dokuments
Vialette, Université Paris-Est
|Wednesday, November 27, 2013, 10:15 a.m., TU
Hochhaus, 5th floor, room
The shuffle u shuffle v of words u and v over alphabet A is the finite set of all words obtainable from merging the words u and v from left to right, but choosing the next symbol arbitrarily from u or v. The shuffle of two words u and v is the language u shuffle v consisting of all words u_1 v_1 u_2 v_2 ... u_k v_k, where k >= 0 and the u_i and the v_i are the words such that u = u_1 u_2 ... u_k and v = v_1 v_2 ... v_k. It is well-known that it can be tested in polynomial time whether or not u is in v_1 shuffle v_2 for given words u, v_1 and v_2 [J.-C. Spehner, Le Calcul Rapide des Mélanges de Deux Mots, TCS, 1986]. In this talk we consider the problem of determining whether or not a word u is a square for the shuffle product (i.e, there exists v such that u is in v shuffle v). Our approach is to represent words as linear graphs in which deciding whether or not a given word is a square for the shuffle product reduces to computing some constrained perfect matching. We shall also extend our approach to some related problems and propose future lines of research.