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. (VZ VERIFIT)
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 prodeterminizace čí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íhopří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 natřídách znaků, které jsou běžné v praxi. Naší hlavní motivací je (kroměaplikace ve verifikaci a rozhodovacích procedurách logik) aplikacedeterministický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 napraktických benchmarcích z těchto aplikačních domén a usoudili jsme, že vesrovná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/"
}
Soubory
Nahoru