Questions tagged [omega-automata]
The omega-automata tag has no usage guidance.
7
questions
2
votes
1
answer
36
views
Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?
Let $L$ be the language of infinite words in $\{0,1\}^\omega$ such that any finite prefix of a word in $L$ has at least as many $0$'s as $1$'s. Is $L$ büchi recognisable?
I think that $L$ is not $\...
- 23
3
votes
1
answer
41
views
Complementation of deterministic Streett automata
There are a lot of work about bounds on the complementation of Streett automata (see e.g. this paper). They talk about the general setting of nondeterministic Streett automata. But what about ...
- 448
2
votes
1
answer
45
views
$\omega$-automata where string is accepted iff a final state is accessible from starting state
I am wondering if $\omega$-automata with the following acceptance condition are valid.
An input string is accepted iff one of the final states occurs at least once.
This differs from Buchi automata in ...
3
votes
1
answer
76
views
Equivalence of states between two "quasi-deterministic" strongly connected Büchi automata accepting the same $\omega$-language
Hope someone can point me to the right direction to solve this problem.
Premise.
I call quasi-deterministic Büchi automaton (qDBA) a Büchi automaton $B = \langle S, \Sigma, S_0, \delta, F \rangle$, ...
- 33
2
votes
0
answers
119
views
Intersection of two deterministic parity automata
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
- 391
0
votes
1
answer
68
views
Counterexample for simple parity automaton reduction
I am dealing with deterministic parity automata and state space reduction (not minimization).
If we define $\equiv_L$ to be the equivalence relation that sets two states equal iff starting from those ...
- 625
1
vote
2
answers
92
views
Language equivalent states in a deterministic parity automaton
Given a deterministic parity automaton $\mathcal{A}$ with state set $Q$ and a state $q \in Q$, we denote with $\mathcal{A}_q$ the same automaton with initial state $q$. Two states $p$ and $q$ are ...
- 625