direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Gastvorträge 2013

On Recognizing Words That Are Squares for the Shuffle Product
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.


Vincent Froese, Fachgebiet Algorithmik und Komplexitätstheorie

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Research Colloquium

Algorithmik und Komplexitätstheorie