1
$\begingroup$

Given a set of strings $S$ over $\{a,b\}$. How to determine whether there is an infinite sequence consisting of ${a, b}$ (i.e., a $\omega$-string), which doesn't have any string in $S$ as a substring?

The total length of all substrings in $S$ is at most $20000$.

$\endgroup$
4
  • $\begingroup$ Are you looking for an efficient algorithm, or for any algorithm? $\endgroup$ Oct 19 '20 at 18:12
  • $\begingroup$ In general, I am looking for an efficient algorithm, but if you have any ideas on any algorithm, it may have been useful for me. $\endgroup$
    – Kapa
    Oct 19 '20 at 18:24
  • 1
    $\begingroup$ Construct a DFA for the language of all finite strings not containing any of the given strings as a substring. Check whether there is a reachable state which belongs to a cycle containing only accepting states. This algorithm runs in exponential time. $\endgroup$ Oct 20 '20 at 6:35
  • 2
    $\begingroup$ What's the motivation for this question? What's the context in which you encountered it? $\endgroup$
    – D.W.
    Oct 20 '20 at 16:17
1
$\begingroup$

If every $\omega$-string contains a substring in $S$, then we say that $S$ is unavoidable or a universal hitting set (UHS). There is a classical algorithm for detecting whether a set of substrings is unavoidable, described for example in Lothaire's Algebraic combinatorics on words, Section 1.6.

Construct a graph $G$ as follows. The vertices are all prefixes of strings in $S$. For every prefix $p$ and symbol $\sigma$, we connect $p$ to the longest suffix of $p\sigma$ appearing in the graph. The set $S$ is unavoidable iff every cycle in $G$ passes through a vertex corresponding to a word in $S$.

To see this, suppose first that every cycle in $G$ passes through a vertex corresponding to a word in $S$. Consider some $\omega$-word $w$. Starting at the vertex $\epsilon$, "read" the symbols of $w$ one by one. Eventually you will hit a cycle (since $G$ is finite). By assumption, this cycle contains a vertex $v$ in $S$, and so $w$ contains $v$. In the other direction, tracing an $S$-less cycle (replacing each edge by the symbol $\sigma$ used to create it) results in a periodic $\omega$-word which avoids $S$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.