direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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

Back to the research colloquium site.

Zusatzinformationen / Extras