Seminator 2 Can Complement Generalized Büchi Automata via Improved Semi-determinization
Open Access
- 14 July 2020
- book chapter
- Published by Springer Nature
- Vol. 12225, 15-27
Abstract
We present the second generation of the tool Seminator that transforms transition-based generalized Büchi automata (TGBAs) into equivalent semi-deterministic automata. The tool has been extended with numerous optimizations and produces considerably smaller automata than its first version. In connection with the state-of-the-art LTL to TGBAs translator Spot, Seminator 2 produces smaller (on average) semi-deterministic automata than the direct LTL to semi-deterministic automata translator ltl2ldgba of the Owl library. Further, Seminator 2 has been extended with an improved NCSB complementation procedure for semi-deterministic automata, providing a new way to complement automata that is competitive with state-of-the-art complementation tools.Keywords
This publication has 24 references indexed in Scilit:
- One Theorem to Rule Them All2018
- A Simple and Optimal Complementation Algorithm for Büchi Automata2018
- Advanced automata-based algorithms for program termination checkingACM SIGPLAN Notices, 2018
- From LTL and Limit-Deterministic Büchi Automata to Deterministic Parity Automata2017
- Spot 2.0 — A Framework for LTL and $\omega $ -Automata Manipulation2016
- Complementing Semi-deterministic Büchi Automata2016
- Compositional Approach to Suspension and Other Improvements to LTL TranslationLecture Notes in Computer Science, 2013
- Optimizing Büchi Automata2000
- Property specification patterns for finite-state verification1998
- Verifying temporal properties of finite-state probabilistic programs1988