TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 1 27.11.2013


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.

27.11.2013 10:15
Stéphane Vialette
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe