As of May 31, 2023, we have updated our Code of Conduct.

# Tag Info

Accepted

### Does a given regular language contain an infinite prefix-free subset?

Your problem can be solved in polynomial time. To begin, convert the given NFA to an equivalent NFA with the following additional properties: There are no epsilon transitions All states are ...
Accepted

### Algebraic characterisation of star-free safety languages

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

### Is there any equation-based method for transforming Büchi-automata to omega-regular language?

Sure. In fact, the translation from Büchi automata to $\omega$-regular expressions is only a small extension of the one for finite-word languages. Recall that an $\omega$-regular expression is of the ...
Accepted

### Intersection of two deterministic parity automata

The following paper: http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf shows that the intersection (and union) of deterministic parity automata may involve an exponential blowup. Thus, ...
Accepted

Once you have the bound $2^{2n^2}$ on the number of classes, you can note that each state in the complement automaton corresponds to an $\omega$-regular language of the form $L_{f}L_{g}^\omega$, with $... 3 votes ### Algebraic characterisation of star-free safety languages 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 ... 3 votes Accepted ### Decomposition of safety and liveness properties Yes. The automata in question are often called "Looping" automata (so you have a keyword to start from). A possible starting point is the following paper: https://faculty.idc.ac.il/udiboker/... 2 votes Accepted ### Regular safety properties and bad prefixes of$\omega$-regular properties Your construction for bad prefixes is not correct on NBA's. For instance take the NBA on alphabet$A=\{a,b\}$with two initial states$q_a$and$q_b$where for both$x\in A$,$q_x$goes to an ... 2 votes Accepted ### Subsets of$\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata The conjecture does not hold: Let$L$be the set of prefixes of$(c^*ac^*b)^*$. Then$L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$. Take the word$\eta=(c^1ac^1b)(c^2ac^2b)(c^...
Definitions Definition 1: Let $S$ be a set of words. We say that $S$ is nicely infinite prefix-free (made up name for the purpose of this answer) if there are words $u_0,\dots,u_n,\dots$ and \$v_1,\...