39 citations · 255 across the 76 of their papers we have counts for
8 papers · 1 filter
Lower Bounds for the Number of Repetitions in 2D Strings
Paweł Gawrychowski, Samah Ghazawi, Gad M. Landau
A two-dimensional string is simply a two-dimensional array. We continue the study of the combinatorial properties of repetitions in such strings over the binary alphabet, namely th…
The Theory of Universal Graphs for Infinite Duration Games
Thomas Colcombet, Nathanaël Fijalkow, Paweł Gawrychowski +1
We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part w…
Efficiently Testing Simon's Congruence
Pawel Gawrychowski, Maria Kosche, Tore Koss +2
Simon's congruence is defined as follows: two words are -equivalent if they have the same set of subsequences of length at most . We propose an algorithm which…
Distinct Squares in Circular Words
Mika Amit, Paweł Gawrychowski
A circular word, or a necklace, is an equivalence class under conjugation of a word. A fundamental question concerning regularities in standard words is bounding the number of dist…
Existential length universality
Paweł Gawrychowski, Martin Lange, Narad Rampersad +2
We study the following natural variation on the classical universality problem: given a language represented by (e.g., a DFA/RE/NFA/PDA), does there exist an integer $\e…
Testing k-binomial equivalence
Dominik D. Freydenberger, Pawel Gawrychowski, Juhani Karhumäki +2
Two words and are said to be -binomial equivalent if every non-empty word of length at most over the alphabet of and appears as a scattered facto…