Publication detail

Simplifying Alternating Automata for Emptiness Testing

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

Original Title

Simplifying Alternating Automata for Emptiness Testing

Type

conference paper

Language

English

Original Abstract

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.

Keywords

alternating automata, language emptyness, determinisation

Authors

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

Released

12. 10. 2021

Publisher

Springer International Publishing

Location

Cham

ISBN

978-3-030-89051-3

Book

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

Pages from

243

Pages to

264

Pages count

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