Publication Details

Succinct Determinisation of Counting Automata via Sphere Construction (Technical Report)

HOLÍK Lukáš, HOLÍKOVÁ Lenka, LENGÁL Ondřej, SAARIKIVI Olli, VEANES Margus and VOJNAR Tomáš. Succinct Determinisation of Counting Automata via Sphere Construction (Technical Report). Ithaca: Cornell University Library, 2019. Available from: http://arxiv.org/abs/1910.01996
Czech title
Stručná reprezentace čítačových automatů prostřednictvím konstrukce koulí (technická zpráva)
Type
technical report
Language
english
Authors
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Holíková Lenka, Ing. (DITS FIT BUT)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Saarikivi Olli (MSR)
Veanes Margus (MSR)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
URL
Keywords

counting automata, determinisation, regular expressions with bounded repetition

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 naive 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 naive 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
1-19
Publisher
Cornell University Library
Place
Ithaca, DE
DOI
10.48550/arXiv.1910.01996
BibTeX 
@TECHREPORT{FITPUB12673,
   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 (Technical Report)",
   pages = "1--19",
   year = 2019,
   location = "Ithaca, DE",
   publisher = "Cornell University Library",
   doi = "10.48550/arXiv.1910.01996",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12673"
}
Back to top