Questions tagged [omega-automata]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
39 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
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 ...
gigabytes's user avatar
  • 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 ...
Ender_The_Xenocide's user avatar
3 votes
1 answer
77 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
0 answers
120 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
0 votes
1 answer
69 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
  • 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 ...
Andreas T's user avatar
  • 625