Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
It is known that star-free languages are definable by aperiodic syntactic monoids.
But is there any algebraic characterisation of star-free safety $\omega$-languages?
Edit: A language $L$ is safety if it is sufficient to look for a finite prefix of a string $s$ to tell that $s\not\in L$.
On infinite words, automata are much more convenient than Wilke algebra (playing the role of monoids) to characterize safety. Indeed, it just corresponds to being accepted by an automaton where all runs are accepting. This is because automata are designed to append new content to the right, while in Wilke Algebra you can more naturally append to the left.
If you insist on working with Wilke algebra, a characterization of safety languages can look like the following:
Let $(M_f,M_\omega)$ be the syntactic Wilke Algebra of a regular $\omega$-language $L$, and $P\subseteq M_\omega$ be the accepted subset. Recall that each element in $M_f$ represents a set of finite words, and each element of $M_\omega$ a set of infinite words. The subset $P$ of $M_\omega$ corresponds to infinite words in $L$. These sets come with three operations: a product $M_f\times M_f\to M_f$, a mixed product $M_f\times M_\omega\to M_\omega$, and an $\omega$-power $M_f\to M_\omega$.
Then $L$ is safety if and only if there exists a set $B\subseteq M_f$ (the set of "bad prefixes"), such that
Proof: If $L$ is a safety language, we take for $B$ the set of bad prefixes, ie the images of words $u$ that are not prefixes of any word in $L$. This is well-defined, as bad prefixes form a union of Myhill-Nerode equivalence classes: if $u\equiv v$, then either both or none are bad prefixes. Let $x,e\in M_f$ with $e$ idempotent, and $u_x,u_e$ be finite words mapped to these elements. Then $xe^\omega\notin P \Leftrightarrow u_xu_e^\omega\notin L\Leftrightarrow u_xu_e^k\text{ is a bad prefix for some $k\geq 1$}\Leftrightarrow xe\in B$.
Conversely, assume that a set $B$ verifying the above conditions exists, we prove that the language $L$ is safety, and its bad prefixes are the set $B'$ of words mapped into $B$. Let $v$ be an infinite word, by Ramsey theorem $v$ can be decomposed into $u_0u_1u_2\dots$ where $u_0$ is mapped to an element $x\in M_f$, and $u_1,u_2,...$ are mapped to the same idempotent element $e$ (notice that here we need the set $M_f$ to be finite). The word $v$ is then mapped to $xe^\omega$. Now, our hypothesis states that $v\notin L$ if and only if $xe\in B$, which means $v\notin L$ if and only if $u_0u_1\in B'$. Moreover,if $u_0u_1\notin B'$, then no prefix of $v$ is in $B'$, using the property $B\cdot M_f\subseteq B$, and the fact that $u_0\dots u_k$ is mapped to $xe$ for all $k\geq 1$. Therefore $L$ is exactly the set of words not containing a prefix in $B'$, so $L$ is safety. $\square$
Aperiodicity is orthogonal to that, so your star-free safety languages will just be characterized by Wilke algebra that are both safety (in the above sense) and aperiodic.
Denis's excellent answer mentions that aperiodicity is orthogonal to safety, so as long as this is allowed, one can also take a topological view instead of a purely algebraic:
Safety languages can be characterized as the closed sets in a natural topology over infinite words (https://link.springer.com/content/pdf/10.1007%2F978-3-642-58041-3_5.pdf)
Thus, the set you are interested in are the aperiodic languages that are also closed sets.
