Detail publikačního výsledku

Succinct Determinisation of Counting Automata via Sphere Construction

HOLÍK, L.; HOLÍKOVÁ, L.; LENGÁL, O.; VOJNAR, T.; SAARIKIVI, O.; VEANES, M.

Originální název

Succinct Determinisation of Counting Automata via Sphere Construction

Anglický název

Succinct Determinisation of Counting Automata via Sphere Construction

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální abstrakt

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 nave 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 thenave approach, our algorithm is much less prone to explode, produces automatathat can be several orders of magnitude smaller, and is overall faster. 

Anglický abstrakt

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 nave 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 thenave approach, our algorithm is much less prone to explode, produces automatathat can be several orders of magnitude smaller, and is overall faster. 

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

HOLÍK, L.; HOLÍKOVÁ, L.; LENGÁL, O.; VOJNAR, T.; SAARIKIVI, O.; VEANES, M.

Rok RIV

2020

Vydáno

02.12.2019

Nakladatel

Springer Verlag

Místo

Berlin Heidelberg

Kniha

In Proc. of 17th Asian Symposium on Programming Languages and Systems - APLAS'19

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Číslo

11893

Stát

Spolková republika Německo

Strany od

468

Strany do

489

Strany počet

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/"
}

Dokumenty

counting-mata-aplas