Publication Details
Simplifying Alternating Automata for Emptiness Testing
alternating automata, language emptyness, determinisation
We propose preprocessing techniques that improve efficiency of testing language
emptiness of alternating automata. We target mainly automata that come from
practical application such as processing regular expressions, LTL formulae, or
string solving. Such automata often have large alphabets and transition relations
represented by succinct and complex Boolean formulae that are more or less
unrestricted and may even mix symbols with states. Our main contribution are
simplification methods that can be seen as originating from a limited form of
determinisation. Our transformations simplify the transition formulae and
decrease the number of states. We evaluate experimentally that our preprocessing
is beneficial when used together with most of the existing algorithms. It
generally improves running times and allows to solve examples that could not be
solved before within the given timeout.
@inproceedings{BUT176374,
author="Lukáš {Holík} and Pavol {Vargovčík}",
title="Simplifying Alternating Automata for Emptiness Testing",
booktitle="Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings",
year="2021",
pages="243--264",
publisher="Springer International Publishing",
address="Cham",
doi="10.1007/978-3-030-89051-3\{_}14",
isbn="978-3-030-89051-3",
url="https://doi.org/10.1007/978-3-030-89051-3_14"
}