Succinct Determinisation of Counting Automata via Sphere Construction

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F19%3APU135183" target="_blank" >RIV/00216305:26230/19:PU135183 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.fit.vut.cz/research/publication/12077/" target="_blank" >https://www.fit.vut.cz/research/publication/12077/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-34175-6_24" target="_blank" >10.1007/978-3-030-34175-6_24</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Succinct Determinisation of Counting Automata via Sphere Construction

Popis výsledku v původním jazyce

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. 

Název v anglickém jazyce

Succinct Determinisation of Counting Automata via Sphere Construction

Popis výsledku anglicky

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. 

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

ISBN

—

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

22

Strana od-do

468-489

Název nakladatele

Springer Verlag

Místo vydání

Berlin Heidelberg

Místo konání akce

Bali

Datum konání akce

1. 12. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000611530200024