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)

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