Complementing Büchi Automata with Ranker
Open Access
- 6 August 2022
- book chapter
- Published by Springer Nature
- p. 188-201
Abstract
We present the toolRankerfor complementing Büchi automata (BAs).Rankerbuilds on our previous optimizations of rank-based BA complementation and pushes them even further using numerous heuristics to produce even smaller automata. Moreover, it contains novel optimizations of specialized constructions for complementing (i) inherently weak automata and (ii) semi-deterministic automata, all delivered in a robust tool. The optimizations significantly improve the usability ofRanker, as shown in an extensive experimental evaluation with real-world benchmarks, whereRankerproduced in the majority of cases a strictly smaller complement than other state-of-the-art tools.Keywords
This publication has 31 references indexed in Scilit:
- GOAL for Games, Omega-Automata, and LogicsLecture Notes in Computer Science, 2013
- Büchi Complementation and Size-Change Termination2009
- Five Determinisation Algorithms2008
- On-the-Fly Stuttering in the Construction of Deterministic ω-Automata2007
- From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity AutomataLogical Methods in Computer Science, 2007
- BÜCHI COMPLEMENTATION MADE TIGHTERInternational Journal of Foundations of Computer Science, 2006
- Experimental Evaluation of Classical Automata ConstructionsLecture Notes in Computer Science, 2005
- Weak alternating automata are not that weakACM Transactions on Computational Logic, 2001
- The complementation problem for Büchi automata with applications to temporal logicTheoretical Computer Science, 1987
- Alternating finite automata on ω-wordsTheoretical Computer Science, 1984