Publication Details

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.
Czech title
Stručná reprezentace čítačových automatů prostřednictvím konstrukce koulí
Type
conference paper
Language
English
Authors
Holík Lukáš, doc. Mgr., Ph.D. (DITS)
Holíková Lenka, Ing., Ph.D. (RG VERIFIT)
Lengál Ondřej, Ing., Ph.D. (DITS)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
SAARIKIVI, O.
Veanes Margus
Keywords

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

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. 

Published
2019
Pages
468–489
Journal
Lecture Notes in Computer Science, no. 11893, ISSN 0302-9743
Proceedings
In Proc. of 17th Asian Symposium on Programming Languages and Systems - APLAS'19
Conference
17th Asian Symposium on Programming Languages and Systems -- APLAS'19, Bali, ID
Publisher
Springer Verlag
Place
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/"
}
Files
Back to top