Detail výsledku

Simplifying Alternating Automata for Emptiness Testing

HOLÍK, L.; VARGOVČÍK, P. Simplifying Alternating Automata for Emptiness Testing. In Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings. Cham: Springer International Publishing, 2021. p. 243-264. ISBN: 978-3-030-89051-3.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Abstrakt

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.

Klíčová slova

alternating automata, language emptyness, determinisation

URL
Rok
2021
Strany
243–264
Sborník
Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings
Konference
19th Asian Symposium on Programming Languages and Systems -- APLAS'21
ISBN
978-3-030-89051-3
Vydavatel
Springer International Publishing
Místo
Cham
DOI
UT WoS
000783821500014
EID Scopus
BibTeX
@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"
}
Projekty
Automaty v rozhodovacích procedurách a verifikaci, GAČR, Standardní projekty, GA19-24397S, GA19-24397S, zahájení: 2019-01-01, ukončení: 2021-12-31, řešení
Spolehlivé, bezpečné a efektivní počítačové systémy, VUT, Vnitřní projekty VUT, FIT-S-20-6427, zahájení: 2020-03-01, ukončení: 2023-02-28, ukončen
Výzkumné skupiny
Pracoviště
Nahoru