Detail publikace

Simplifying Alternating Automata for Emptiness Testing

HOLÍK Lukáš a VARGOVČÍK Pavol. 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, s. 243-264. ISBN 978-3-030-89051-3. Dostupné z: https://doi.org/10.1007/978-3-030-89051-3_14
Název česky
Zjednodušení alternujících automatů pro testování prázdnosti
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Vargovčík Pavol, Ing. (UITS FIT VUT)
URL
Klíčová slova

alternující automaty, prázdnost jazyka, determinizace

Abstrakt

Navrhli jsme techniky předzpracování, které zlepšují efektivnost testování prázdnosti jezyků alternujících automatů. Zaměřili jsme se především na automaty, které pochází z praxe jako je zpracování regulárních výrazů, nebo LTL formule. Takovéto automaty mají často velkou abecedu a mnoho přechodů reprezentovanou stručnými a komplexními Booleanovými formulemi, které jsou více méně neomezené a můžou kombinovat symboly se stavy. Hlavním přínosem jsou zjednodušující metody, které se můžou pocházet z omezené formy determinizace.  Naše transformace zjednodušují přechodové formule a snižují počet stavů. Experimentálně jsme zjistili, že naše předzpracování je přínosné, pokud je použito společně s většinou existujících algoritmů. Obecně zkracují dobu běhu a umožňují řešit příklady, které dříve nebylo možné vyřešit v daném časovém limitu.

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, Chicago, US
ISBN
978-3-030-89051-3
Vydavatel
Springer International Publishing
Místo
Cham, DE
DOI
10.1007/978-3-030-89051-3_14
UT WoS
000783821500014
EID Scopus
2-s2.0-85118185687
BibTeX 
@INPROCEEDINGS{FITPUB12675,
   author = "Luk\'{a}\v{s} Hol\'{i}k and Pavol Vargov\v{c}\'{i}k",
   title = "Simplifying Alternating Automata for Emptiness Testing",
   pages = "243--264",
   booktitle = "Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings",
   year = 2021,
   location = "Cham, DE",
   publisher = "Springer International Publishing",
   ISBN = "978-3-030-89051-3",
   doi = "10.1007/978-3-030-89051-3\_14",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12675"
}
Nahoru