Publication Details

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

HOLÍK, L.; HOLÍKOVÁ, L.; LENGÁL, O.; VOJNAR, T.; SAARIKIVI, O.; VEANES, M. Succinct Determinisation of Counting Automata via Sphere Construction (Technical Report). Ithaca: Cornell University Library, 2019. p. 1-19.
Czech title
Stručná reprezentace čítačových automatů prostřednictvím konstrukce koulí (technická zpráva)
Type
report
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
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 avoidsunfolding counters into control states, unlike the naive approach, and thus producesmuch smaller deterministic automata. We also develop a simplified and fasterversion 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 inpractice. Our main motivation is (besides applications in verification and decisionprocedures of logics) the application of deterministic (M)CAs in pattern matchingregular expressions with counting, which are very common in e.g. network trafficprocessing and log analysis. We have evaluated our algorithm against practicalbenchmarks from these application domains and concluded that compared to thenaive approach, our algorithm is much less prone to explode, produces automatathat can be several orders of magnitude smaller, and is overall faster.

Published
2019
Pages
1–19
Publisher
Cornell University Library
Place
Ithaca
DOI
10.48550/arXiv.1910.01996
BibTeX 
@techreport{BUT185112,
  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 (Technical Report)",
  year="2019",
  publisher="Cornell University Library",
  address="Ithaca",
  pages="1--19",
  doi="10.48550/arXiv.1910.01996",
  url="http://arxiv.org/abs/1910.01996"
}
Back to top