Tight bounds for complementing parity automata

DOI10.1007/978-3-662-44522-8_42MaRDI QIDQ2922043zbMATH 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/1406.1090

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We follow a connection between tight determinisation and complementation and establish a complementation procedure from parity automata to nondeterministic B"uchi automata and prove it to be tight up to an $O(n)$ factor, where $n$ is the size of the nondeterministic parity automaton. This factor does not depend on the number of priorities.

Recommendations

• Tight upper bounds for Streett and parity complementation
• Tight Bounds for the Determinisation and Complementation of Generalised Büchi Automata
• Büchi complementation made tight
• A tighter analysis of Piterman's Büchi determinization
• BÜCHI COMPLEMENTATION MADE TIGHTER

Cited in

(7)

• Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
• Tight upper bounds for Streett and parity complementation
• Bounded Parikh automata
• Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
• scientific article; zbMATH DE number 7298596 (Why is no real title available?)
• Determinising parity automata
• Complementation of Emerson-Lei automata

This page was built for publication: Tight bounds for complementing parity automata

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