Page Content
to Navigation
On Recognizing Words That Are Squares for the Shuffle Product
Stéphane Vialette (Université Paris-Est Marne-la-Vallée)
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.
Date | Speaker | Location | Language |
---|---|---|---|
27.11.2013 10:15 | Stéphane Vialette | TEL 512 | english |