Přístupnostní navigace
E-application
Search Search Close
Publication detail
HOLÍK, L. HOLÍKOVÁ, L. LENGÁL, O. VOJNAR, T. SAARIKIVI, O. VEANES, M.
Original Title
Succinct Determinisation of Counting Automata via Sphere Construction
Type
conference paper
Language
English
Original Abstract
We propose an efficient algorithm for determinising counting automata (CAs), i.e., finite automata extended with bounded counters. The algorithm avoids unfolding counters into control states, unlike the nave approach, and thus produces much smaller deterministic automata. We also develop a simplified and faster version of the general algorithm for the sub-class of so-called monadic CAs (MCAs), i.e., CAs with counting loops on character classes, which are common in practice. Our main motivation is (besides applications in verification and decision procedures of logics) the application of deterministic (M)CAs in pattern matching regular expressions with counting, which are very common in e.g. network traffic processing and log analysis. We have evaluated our algorithm against practical benchmarks from these application domains and concluded that compared to the nave approach, our algorithm is much less prone to explode, produces automata that can be several orders of magnitude smaller, and is overall faster.
Keywords
automata, counter automata, finite automata, XML schema, regular expressions, determinization
Authors
HOLÍK, L.; HOLÍKOVÁ, L.; LENGÁL, O.; VOJNAR, T.; SAARIKIVI, O.; VEANES, M.
Released
2. 12. 2019
Publisher
Springer Verlag
Location
Berlin Heidelberg
ISBN
0302-9743
Periodical
Lecture Notes in Computer Science
Number
11893
State
Federal Republic of Germany
Pages from
468
Pages to
489
Pages count
22
URL
https://www.fit.vut.cz/research/publication/12077/
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/" }