Questions tagged [omega-automata]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
40 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 ...
user avatar
3 votes
1 answer
70 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$, ...
user avatar
  • 33
2 votes
0 answers
111 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 ...
user avatar
  • 401
0 votes
1 answer
67 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 ...
user avatar
  • 615
1 vote
2 answers
77 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 ...
user avatar
  • 615