Questions tagged [omega-automata]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
43 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 ...
Nicola Gigante's user avatar
3 votes
1 answer
81 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$, ...
Davide's user avatar
  • 33
2 votes
1 answer
48 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 ...
Ender_The_Xenocide's user avatar
2 votes
1 answer
51 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 $\...
Jerry Tao's user avatar
2 votes
0 answers
121 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 ...
kafka's user avatar
  • 391
1 vote
2 answers
99 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 ...
Andreas T's user avatar
  • 635
0 votes
1 answer
71 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 ...
Andreas T's user avatar
  • 635