A Simple and Optimal Complementation Algorithm for Büchi Automata

DOI10.1145/3209108.3209138zbMath1497.68246OpenAlexW2798623107MaRDI QIDQ5145275

Joel D. Allred, Ulrich Ultes-Nitsche

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3209108.3209138

zbMATH Keywords

complementationbenchmarkingBüchi automatonoptimal upper bound

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Formal languages and automata (68Q45)

Related Items

Towards a grand unification of Büchi complementation constructions, One-pass and tree-shaped tableau systems for TPTL and \(\mathrm{TPTL_b+Past}\)