Questions tagged [omega-automata]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer

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 $\...
3 votes
1 answer

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

$\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

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

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

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

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