Detail publikace

Succinct Determinisation of Counting Automata via Sphere Construction

HOLÍK Lukáš, HOLÍKOVÁ Lenka, LENGÁL Ondřej, SAARIKIVI Olli, VEANES Margus a VOJNAR Tomáš. Succinct Determinisation of Counting Automata via Sphere Construction. In: In Proc. of 17th Asian Symposium on Programming Languages and Systems - APLAS'19. Berlin Heidelberg: Springer Verlag, 2019, s. 468-489. ISSN 0302-9743.
Název česky
Stručná reprezentace čítačových automatů prostřednictvím konstrukce koulí
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Holíková Lenka, Ing. (UITS FIT VUT)
Lengál Ondřej, Ing., Ph.D. (UITS FIT VUT)
Saarikivi Olli (MSR)
Veanes Margus (MSR)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT)
Abstrakt

Navrhli jsme efektivní algoritmus pro determinizace čítačových automatů, např. konečných automatů rozšířených o omezené čítače. Algoritmus nerozvijí čítače do kontrolních stavů, na rozdíl od naivního přístupu, a tak vytváří menší deterministické automaty. Vytvořili jsme také zjednodušenou a rychlejší verzi obecného algoritmu pro podtřídu tzv. monadických čítačových automatů, např. čítačových automatů s čítací smyčkou na třídách znaků, které jsou běžné v praxi. Naší hlavní motivací je (kromě aplikace ve verifikaci a rozhodovacích procedurách logik) aplikace deterministických monadických čítačových automatů ve vyhledávání vzorů regulárních výrazů s počítáním, které je běžné např. ve zpracování síťového provozu nebo při analýze logů. Náš algoritmus jsme otestovali na praktických benchmarcích z těchto aplikačních domén a usoudili jsme, že ve srovnání s naivním přístupem je náš algoritmus méně náchylný k explozi, vytváří automaty, které jsou o řád menší, a je celkově rychlejší.

Rok
2019
Strany
468-489
Časopis
Lecture Notes in Computer Science, č. 11893, ISSN 0302-9743
Sborník
In Proc. of 17th Asian Symposium on Programming Languages and Systems - APLAS'19
Konference
17th Asian Symposium on Programming Languages and Systems -- APLAS'19, Bali, ID
Vydavatel
Springer Verlag
Místo
Berlin Heidelberg, DE
DOI
10.1007/978-3-030-34175-6_24
UT WoS
000611530200024
EID Scopus
2-s2.0-85076674258
BibTeX 
@INPROCEEDINGS{FITPUB12077,
   author = "Luk\'{a}\v{s} Hol\'{i}k and Lenka Hol\'{i}kov\'{a} and Ond\v{r}ej Leng\'{a}l and Olli Saarikivi and Margus Veanes and Tom\'{a}\v{s} Vojnar",
   title = "Succinct Determinisation of Counting Automata via Sphere Construction",
   pages = "468--489",
   booktitle = "In Proc. of 17th Asian Symposium on Programming Languages and Systems - APLAS'19",
   journal = "Lecture Notes in Computer Science",
   number = 11893,
   year = 2019,
   location = "Berlin Heidelberg, DE",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-030-34175-6\_24",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12077"
}
Nahoru