Deciding Nondeterministic Hierarchy of Deterministic Tree Automata | Zendy

Damian Niwiński | Zendy; Igor Walukiewicz | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Deciding Nondeterministic Hierarchy of Deterministic Tree Automata

Author(s) -

Damian Niwiński,

Igor Walukiewicz

Publication year - 2005

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2004.05.015

Subject(s) - nondeterministic algorithm , deterministic automaton , two way deterministic finite automaton , büchi automaton , discrete mathematics , mathematics , automaton , nondeterministic finite automaton , emptiness , deterministic finite automaton , computer science , combinatorics , theoretical computer science , algorithm , automata theory , philosophy , theology

We show an algorithm which, for a given deterministic parity automaton on infinite trees, computes the minimal Mostowski (or Rabin) index of a nondeterministic automaton recognizing the same language. This extends a previous result of Urbański on deciding if a given deterministic Rabin automaton is equivalent to a nondeterministic Büchi automaton. The algorithm runs in the time of verifying the non-emptiness of nondeterministic parity automata

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research