<p>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:</p>
<p>Safety languages can be characterized as the closed sets in a natural topology over infinite words (<a href="https://link.springer.com/content/pdf/10.1007%2F978-3-642-58041-3_5.pdf" rel="nofollow noreferrer">https://link.springer.com/content/pdf/10.1007%2F978-3-642-58041-3_5.pdf</a>)</p>
<p>Thus, the set you are interested in are the aperiodic languages that are also closed sets.</p>

CC BY-SA 4.0
2021-10-07T14:12:15.600Z
2021-10-07T14:12:15.600Z
Shaull
<p>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.</p>
<p>If you insist on working with Wilke algebra, a characterization of safety languages can look like the following:</p>
<p>Let <span class="math-container">$(M_f,M_\omega)$</span> be the syntactic Wilke Algebra of a regular <span class="math-container">$\omega$</span>-language <span class="math-container">$L$</span>, and <span class="math-container">$P\subseteq M_\omega$</span> be the accepted subset. Recall that each element in <span class="math-container">$M_f$</span> represents a set of finite words, and each element of <span class="math-container">$M_\omega$</span> a set of infinite words. The subset <span class="math-container">$P$</span> of <span class="math-container">$M_\omega$</span> corresponds to infinite words in <span class="math-container">$L$</span>. These sets come with three operations: a product <span class="math-container">$M_f\times M_f\to M_f$</span>, a mixed product <span class="math-container">$M_f\times M_\omega\to M_\omega$</span>, and an <span class="math-container">$\omega$</span>-power <span class="math-container">$M_f\to M_\omega$</span>.</p>
<p>Then <span class="math-container">$L$</span> is safety if and only if there exists a set <span class="math-container">$B\subseteq M_f$</span> (the set of &quot;bad prefixes&quot;), such that</p>
<ul>
<li><span class="math-container">$B\cdot M_f\subseteq B$</span></li>
<li>for all <span class="math-container">$x,e\in M_f$</span> with <span class="math-container">$e$</span> idempotent, we have <span class="math-container">$xe^\omega\notin P\Leftrightarrow xe\in B$</span></li>
</ul>
<p><strong>Proof:</strong>
If <span class="math-container">$L$</span> is a safety language, we take for <span class="math-container">$B$</span> the set of bad prefixes, ie the images of words <span class="math-container">$u$</span> that are not prefixes of any word in <span class="math-container">$L$</span>. This is well-defined, as bad prefixes form a union of Myhill-Nerode equivalence classes: if <span class="math-container">$u\equiv v$</span>, then either both or none are bad prefixes. Let <span class="math-container">$x,e\in M_f$</span> with <span class="math-container">$e$</span> idempotent, and <span class="math-container">$u_x,u_e$</span> be finite words mapped to these elements. Then <span class="math-container">$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$</span>.</p>
<p>Conversely, assume that a set <span class="math-container">$B$</span> verifying the above conditions exists, we prove that the language <span class="math-container">$L$</span> is safety, and its bad prefixes are the set <span class="math-container">$B'$</span> of words mapped into <span class="math-container">$B$</span>. Let <span class="math-container">$v$</span> be an infinite word, by Ramsey theorem <span class="math-container">$v$</span> can be decomposed into <span class="math-container">$u_0u_1u_2\dots$</span> where <span class="math-container">$u_0$</span> is mapped to an element <span class="math-container">$x\in M_f$</span>, and <span class="math-container">$u_1,u_2,...$</span> are mapped to the same idempotent element <span class="math-container">$e$</span> (notice that here we need the set <span class="math-container">$M_f$</span> to be finite). The word <span class="math-container">$v$</span> is then mapped to <span class="math-container">$xe^\omega$</span>. Now, our hypothesis states that <span class="math-container">$v\notin L$</span> if and only if <span class="math-container">$xe\in B$</span>, which means <span class="math-container">$v\notin L$</span> if and only if <span class="math-container">$u_0u_1\in B'$</span>. Moreover,if <span class="math-container">$u_0u_1\notin B'$</span>, then no prefix of <span class="math-container">$v$</span> is in <span class="math-container">$B'$</span>, using the property <span class="math-container">$B\cdot M_f\subseteq B$</span>, and the fact that <span class="math-container">$u_0\dots u_k$</span> is mapped to <span class="math-container">$xe$</span> for all <span class="math-container">$k\geq 1$</span>. Therefore <span class="math-container">$L$</span> is exactly the set of words not containing a prefix in <span class="math-container">$B'$</span>, so <span class="math-container">$L$</span> is safety.
<span class="math-container">$\square$</span></p>
<p>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.</p>

CC BY-SA 4.0
2021-10-07T22:42:39.707Z
Thanks! Has this ever appeared in the literature or is it just folklore?
Nicola Gigante
CC BY-SA 4.0
2021-10-07T23:08:13.963Z
I don't know of a source doing this, as I said it is a bit unnatural to characterize safety with monoids when automata are more appropriate. But who knows maybe this characterization might be of interest in some specific context. The ingredients of the proof are quite standard, I would guess this characterization probably appears somewhere, for instance as an exercise in a textbook.
Denis
CC BY-SA 4.0
2021-10-07T13:54:12.693Z
2021-10-07T14:36:16.417Z
2021-10-07T14:36:16.417Z
Denis
<p>It is known that star-free languages are definable by aperiodic syntactic monoids.</p>
<p>But is there any algebraic characterisation of star-free <em>safety</em> <span class="math-container">$\omega$</span>-languages?</p>
<p><strong>Edit</strong>: A language <span class="math-container">$L$</span> is <em>safety</em> if it is sufficient to look for a <em>finite prefix</em> of a string <span class="math-container">$s$</span> to tell that <span class="math-container">$s\not\in L$</span>.</p>

<reference-request><fl.formal-languages><omega-language>
Algebraic characterisation of star-free safety languages
Nicola Gigante
# Algebraic characterisation of star-free safety languages

(Asked by: username_0 on 2021-10-06)

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

**Tags:** reference-request, fl.formal-languages, omega-language


---

## 2 answers

### Answer by username_2 on 2021-10-07. Score: 6 | Accepted answer

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

* $B\cdot M\_f\subseteq B$
* for all $x,e\in M\_f$ with $e$ idempotent, we have $xe^\omega\notin P\Leftrightarrow xe\in B$

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

> **Comments:**
> **username_0**: Thanks! Has this ever appeared in the literature or is it just folklore?  
> **username_2**: I don't know of a source doing this, as I said it is a bit unnatural to characterize safety with monoids when automata are more appropriate. But who knows maybe this characterization might be of interest in some specific context. The ingredients of the proof are quite standard, I would guess this characterization probably appears somewhere, for instance as an exercise in a textbook.  

---

### Answer by username_1 on 2021-10-07. Score: 3

username_2'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.


---

