# $\omega$-string avoiding a set of substrings

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$$.

• Are you looking for an efficient algorithm, or for any algorithm? – Yuval Filmus Oct 19 '20 at 18:12
• 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. – Kapa Oct 19 '20 at 18:24
• 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. – Yuval Filmus Oct 20 '20 at 6:35
• What's the motivation for this question? What's the context in which you encountered it? – D.W. Oct 20 '20 at 16:17

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$$.