Thumbnail
Access Restriction
Open

Author Friedmann, Oliver ♦ Lange, Martin
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Parity Automaton ♦ Ramsey-based Analysis ♦ Chi Automaton ♦ Certain Acceptance Condition ♦ Nondeterministic Parity Automaton ♦ Inclusion Problem ♦ Explicit Ramsey-based Algorithm ♦ Interesting Advantage ♦ Ramsey-based Method ♦ Ramsey-based Algorithm ♦ Decision Problem ♦ Ramsey-based Analysis Procedure ♦ New Algorithm ♦ Parity Condition ♦ Avoids Explicit Complementation ♦ Explicit Complementation ♦ Direct Method ♦ Co-b Chi Condition ♦ Asymptotic Worst-case
Abstract Abstract. Parity automata are a generalisation of Büchi automata that have some interesting advantages over the latter, e.g. determinisability, succinctness and the ability to express certain acceptance conditions like the intersection of a Büchi and a co-Büchi condition directly as a parity condition. Decision problems like universality and inclusion for such automata are PSPACE-complete and have originally been tackled via explicit complementation only. Ramsey-based methods are a later development that avoids explicit complementation but relies on an application of Ramsey’s Theorem for its correctness. In this paper we develop new and explicit Ramsey-based algorithms for the universality and inclusion problem for nondeterministic parity automata. We compare them to Ramsey-based algorithms which are obtained from translating parity automata into Büchi automata first and then applying the known Ramsey-based analysis procedures to the resulting automata. We show that the speed-up in the asymptotic worst-case gained through the new and direct methods is exponential in the number of priorities in the parity automata. We also show that the new algorithms are much more efficient in practice. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article