7 votes
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 ...
Mikhail Rudoy's user avatar
6 votes
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 ...
Denis's user avatar
  • 8,678
6 votes
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 ...
Shaull's user avatar
  • 5,571
4 votes
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, ...
Shaull's user avatar
  • 5,571
4 votes
Accepted

Size bound on Büchi automaton for complement

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 $...
Shaull's user avatar
  • 5,571
4 votes

Minimizing Automata accepting $\omega$-words (i.e. infinite words)

Minimization of automata on infinite words is still a very mysterious problem. Although most of the results are negative, as pointed by Shaull, for example, minimization of DBWs (deterministic Büchi ...
Bader Abu Radi's user avatar
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 ...
Shaull's user avatar
  • 5,571
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/...
Shaull's user avatar
  • 5,571
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^...
Denis's user avatar
  • 8,678
2 votes

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

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,\...
xavierm02's user avatar
  • 556
1 vote

Maximally Permissive Strategies for Safety Properties

In a safety game, the existence of a maximally permissive strategy is easy to show: you always allow all moves that stay in the winning region. This works because safety games are precisely the games ...
Denis's user avatar
  • 8,678

Only top scored, non community-wiki answers of a minimum length are eligible