Determinising parity automata

DOI10.1007/978-3-662-44522-8_41MaRDI QIDQ2922042zbMATH OpenOpenAlexFDO

Authors Sven Schewe, Thomas Varghese

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.5394

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Parity word automata and their determinisation play an important role in automata and game theory. We discuss a determinisation procedure for nondeterministic parity automata through deterministic Rabin to deterministic parity automata. We prove that the intermediate determinisation to Rabin automata is optimal. We show that the resulting determinisation to parity automata is optimal up to a small constant. Moreover, the lower bound refers to the more liberal Streett acceptance. We thus show that determinisation to Streett would not lead to better bounds than determinisation to parity. As a side-result, this optimality extends to the determinisation of B"uchi automata.

Recommendations

• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• Parityizing Rabin and Streett
• scientific article; zbMATH DE number 1701356
• Tighter Bounds for the Determinisation of Büchi Automata
• Tight bounds for complementing parity automata

Cited in

(16)

• -automata
• Index appearance record with preorders
• scientific article; zbMATH DE number 1701356 (Why is no real title available?)
• Bounded Parikh automata
• Ramsey-based analysis of parity automata
• Parityizing Rabin and Streett
• Approximate automata for omega-regular languages
• Computing the Rabin Index of a Parity Automaton
• Good-for-MDPs automata for probabilistic analysis and reinforcement learning
• Rabin vs. Streett automata
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• Register-bounded synthesis
• A survey on satisfiability checking for the \(\mu \)-calculus through tree automata
• From Muller to parity and Rabin qutomata: optimal transformations preserving (history) determinism
• Complementation of Emerson-Lei automata
• Optimal transformations of games and automata using Muller conditions

This page was built for publication: Determinising parity automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922042)