Determinization of $ω$-automata unified

Computer Science – Formal Languages and Automata Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

We describe a uniform construction for converting $\omega$-automata with arbitrary acceptance conditions (based on the notion of infinity sets i.e. the set of states visited infinitely often in a run of the automaton) to equivalent deterministic parity automata (DPW). Given a non-deterministic automaton with $n$ states, our construction gives a DPW with at most $2^{O(n^2 \log n)}$ states and $O(n^2)$ parity indices. The corresponding bounds when the original automaton is deterministic are O(n!) and O(n), respectively. Our algorithm gives better asymptotic bounds on the number of states and parity indices vis-a-vis the best known technique when determinizing Rabin or Streett automata with $\Omega{(2^n)}$ acceptance pairs, where $n > 1$. We demonstrate this by describing a family of Streett (and Rabin) automata with $2^{n}$ non-redundant acceptance pairs, for which the best known determinization technique gives a DPW with at least $\Omega{(2^{(n^3)})}$ states, while our construction constructs a DRW/DPW with $2^{O(n^2\log n)}$ states. An easy corollary of our construction is that an $\omega$-language with Rabin index $k$ cannot be recognized by any $\omega$-automaton (deterministic or non-deterministic) with fewer than $O(\sqrt{k})$ states.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Determinization of $ω$-automata unified does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Determinization of $ω$-automata unified, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determinization of $ω$-automata unified will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-456637

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.