1
$\begingroup$

I am trying to demonstrate the following idea without success.

There are infinitely many $n \in \mathbb{N}$ such that: There is a non-deterministic Buchi automata of size $n$ such that a deterministic Rabin Automata accepting the same language has at least $n!$ states.

Any help would be appreciated

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael♦ Apr 26 '18 at 14:35
4
$\begingroup$

This is Theorem 1.30 in the chapter "Omega-Automata" in the book "Automata, Logics, and Infinite Games: A Guide to Current Research" edited by Erich Grädel, Wolfgang Thomas and Thomas Wilke. They have a proof as well (and a literature referene to the original publication).

Note that instead of the nondeterminstic Buchi automaton having $n$ states, it needs to have $O(n)$ states to make the proof work. The problem is then defined slightly differently to make this precise.

Note that it is a bit confusing if you write "Buchi automata" and "deterministic Rabin automata" in the same question if the former are meant to be "nondeterministic Buchi automata". There is ample work both on deterministic and non-deterministic Buchi automata, so spelling out which variant is meant is important.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

Are you sure you didn't get them mixed up?

It seems like for any Buchi automaton with accepting states F, we can build the equivalent Rabin automaton with accepting conditions $\Omega = \{(\{\}, F)\}$ that accepts the same language.

(I.e., any infinite sequence $\rho$ has to intersect some state in $F$ infinitely often and has no restrictions on what states it can't hit infinitely often.)

I'm using the acceptance condition here https://en.wikipedia.org/wiki/Ω-automaton#Acceptance_conditions. Was there a different formulation you had in mind?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I want a deterministic Rabin Automata $\endgroup$ – Agnishom Chattopadhyay Apr 26 '18 at 5:17
  • 1
    $\begingroup$ This answer would be somewhat more appropriate as a clarifying comment. $\endgroup$ – Yuval Filmus Apr 26 '18 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.