Detail publikačního výsledku

Simplifying Alternating Automata for Emptiness Testing

HOLÍK, L.; VARGOVČÍK, P.

Originální název

Simplifying Alternating Automata for Emptiness Testing

Anglický název

Simplifying Alternating Automata for Emptiness Testing

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální 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.

Anglický 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

Klíčová slova v angličtině

alternating automata, language emptyness, determinisation

Autoři

HOLÍK, L.; VARGOVČÍK, P.

Rok RIV

2022

Vydáno

12.10.2021

Nakladatel

Springer International Publishing

Místo

Cham

ISBN

978-3-030-89051-3

Kniha

Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings

Strany od

243

Strany do

264

Strany počet

22

URL

https://doi.org/10.1007/978-3-030-89051-3_14

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"
}