7
$\begingroup$

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

$\endgroup$
0
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! Has this ever appeared in the literature or is it just folklore? $\endgroup$
    – gigabytes
    Oct 7 at 22:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Denis
    Oct 7 at 23:08
3
$\begingroup$

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.

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