Inhalt des Dokuments
|Stéphane Vialette, Université Paris-Est Marne-la-Vallée|
|Wednesday, November 27, 2013, 10:15 a.m., TU Hochhaus, 5th floor, room 512|
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.
ContactVincent Froese, Fachgebiet Algorithmik und Komplexitätstheorie