Christof Löding ; Sarah Winter.
Regular synchronization languages can be used to define rational relations of
finite words, and to characterize subclasses of rational relations, like
automatic or recognizable relations. We provide a systematic study of the
decidability of uniformization and definability problems for subclasses of
rational relations defined in terms of such synchronization languages. We
rephrase known results in this setting and complete the picture by adding
several new decidability and undecidability results.
Section:
Automata, Logic and Semantics
Aseem Baranwal ; James Currie ; Lucas Mol ; Pascal Ochem ; Narad Rampersad ; Jeffrey Shallit.
The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained by
changing each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is a
nonempty word of the form $x\, \overline{x}$. In this paper, we study infinite
binary words that do not contain arbitrarily large antisquares. For example, we
show that the repetition threshold for the language of infinite binary words
containing exactly two distinct antisquares is $(5+\sqrt{5})/2$. We also study
repetition thresholds for related classes, where "two" in the previous sentence
is replaced by a larger number.
We say a binary word is $\textit{good}$ if the only antisquares it contains
are $01$ and $10$. We characterize the minimal antisquares, that is, those
words that are antisquares but all proper factors are good. We determine the
growth rate of the number of good words of length $n$ and determine the
repetition threshold between polynomial and exponential growth for the number
of good words.
Section:
Combinatorics
Csilla Bujtás ; Pakanun Dokyeesun ; Sandi Klavžar.
In the Maker-Breaker domination game played on a graph $G$, Dominator's goal
is to select a dominating set and Staller's goal is to claim a closed
neighborhood of some vertex. We study the cases when Staller can win the game.
If Dominator (resp., Staller) starts the game, then $\gamma_{\rm SMB}(G)$
(resp., $\gamma_{\rm SMB}'(G)$) denotes the minimum number of moves Staller
needs to win. For every positive integer $k$, trees $T$ with $\gamma_{\rm
SMB}'(T)=k$ are characterized and a general upper bound on $\gamma_{\rm SMB}'$
is proved. Let $S = S(n_1,\dots, n_\ell)$ be the subdivided star obtained from
the star with $\ell$ edges by subdividing its edges $n_1-1, \ldots, n_\ell-1$
times, respectively. Then $\gamma_{\rm SMB}'(S)$ is determined in all the cases
except when $\ell\ge 4$ and each $n_i$ is even. The simplest formula is
obtained when there are at least two odd $n_i$s. If $n_1$ and $n_2$ are the two
smallest such numbers, then $\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil
\log_2(n_1+n_2+1)\rceil$. For caterpillars, exact formulas for $\gamma_{\rm
SMB}$ and for $\gamma_{\rm SMB}'$ are established.
Section:
Graph Theory