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 ...
- 2,758
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 ...
- 8,473
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 ...
- 5,511
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, ...
- 5,511
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 $...
- 5,511
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 ...
- 5,511
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/...
- 5,511
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 ...
- 8,473
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^...
- 8,473
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,\...
- 521
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 ...
- 8,473
Only top scored, non community-wiki answers of a minimum length are eligible