Detail publikace

Succinct Determinisation of Counting Automata via Sphere Construction

HOLÍK, L.; HOLÍKOVÁ, L.; LENGÁL, O.; VOJNAR, T.; SAARIKIVI, O.; VEANES, M. Succinct Determinisation of Counting Automata via Sphere Construction. In In Proc. of 17th Asian Symposium on Programming Languages and Systems - APLAS'19. Lecture Notes in Computer Science. Berlin Heidelberg: Springer Verlag, 2019. p. 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
anglicky
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Holíková Lenka, Ing., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
SAARIKIVI, O.
Veanes Margus
Klíčová slova

automata, counter automata, finite automata, XML schema, regular expressions, determinization

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
DOI
10.1007/978-3-030-34175-6_24
UT WoS
000611530200024
EID Scopus
2-s2.0-85076674258
BibTeX 
@inproceedings{BUT161860,
  author="HOLÍK, L. and HOLÍKOVÁ, L. and LENGÁL, O. and VOJNAR, T. and SAARIKIVI, O. and VEANES, M.",
  title="Succinct Determinisation of Counting Automata via Sphere Construction",
  booktitle="In Proc. of 17th Asian Symposium on Programming Languages and Systems - APLAS'19",
  year="2019",
  journal="Lecture Notes in Computer Science",
  number="11893",
  pages="468--489",
  publisher="Springer Verlag",
  address="Berlin Heidelberg",
  doi="10.1007/978-3-030-34175-6\{_}24",
  issn="0302-9743",
  url="https://www.fit.vut.cz/research/publication/12077/"
}
Nahoru