4 votes
Accepted

$\omega$-automata where string is accepted iff a final state is accessible from starting state

Yes, it was studied before. In one of the early papers on accepting infinitary languages Landweber introduced five acceptance types that included those of Büchi and Muller. On the lowest level where ...
Hendrik Jan's user avatar
  • 30.4k
3 votes
Accepted

Complementation of deterministic Streett automata

This paper gives an example of a deterministic Rabin automaton with $\mathcal{O}(n)$ states such that there is no nondeterministic (hence no deterministic) equivalent Streett automaton with less than $...
Nathaniel's user avatar
  • 13.9k
2 votes

Language equivalent states in a deterministic parity automaton

Two states in the automaton have different languages if and only if there exists a word that is accepted from one state, but not from the other. Checking if this is the case boils down to building a ...
DCTLib's user avatar
  • 2,742
1 vote
Accepted

Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?

As you suspected, $L$ is not büchi recognisable/$\omega$-regular. Here is a proof. Towards a contradiction, suppose $L$ is $\omega$-regular. Then $$L= A_1B_1^\omega\cup A_2B_2^\omega\cup\cdots\cup ...
John L.'s user avatar
  • 38.8k
1 vote
Accepted

Equivalence of states between two "quasi-deterministic" strongly connected Büchi automata accepting the same $\omega$-language

Your property does not hold. Consider the following languages over $\Sigma = \{a,b\}$: There are infinitely many $a$s at even positions in a word There are infinitely many $a$s at odd positions in a ...
DCTLib's user avatar
  • 2,742
1 vote
Accepted

Counterexample for simple parity automaton reduction

After some thought, I found a counter example. It has four states and there might be one with only three states, but this one works too. States 1, 2, and 3 are language equivalent. 1 and 3 also have ...
Andreas T's user avatar
  • 635
1 vote
Accepted

Language equivalent states in a deterministic parity automaton

DCTLib provided a reasonable answer, though it has complexity $n^4 k^2$, which is unsuited for my purpose of use. Another algorithm was proposed to me. From $\mathcal{A}$ with state set $Q$ and ...
Andreas T's user avatar
  • 635

Only top scored, non community-wiki answers of a minimum length are eligible