Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikačního výsledku
ŠEDÝ, M.; HOLÍK, L.
Originální název
Automata Size Reduction by Procedure Finding
Anglický název
Druh
Stať ve sborníku mimo WoS a Scopus
Originální abstrakt
We introduce a novel paradigm for reducing the size of finite automata by compressing repeating sub-graphs. These repeating sub-graphs can be viewed as invocations of a single procedure. Instead of representing each invocation explicitly, they can be replaced by a single procedure that uses a small runtime memory to remember the call context. We elaborate on the technical details of a basic implementation of this idea, where the memory used by the procedures is a simple finite-state register. We propose methods for identifying repetitive sub-graphs, collapsing them into procedures, and measuring the resulting reduction in automata size. Already this basic implementation of reduction by procedure finding yields practically relevant results, particularly in the context of FPGA accelerated pattern matching, where automata size is a primary bottleneck. We achieve a size reduction of up to 70% in automata that had already been minimized using existing advanced methods.
Anglický abstrakt
Klíčová slova
Nondeterministic Finite Automata, Reduction, Regular Expressions, Network Intrusion Detection Systems
Klíčová slova v angličtině
Autoři
Vydáno
08.06.2025
Nakladatel
Springer Nature Switzerland AG
Místo
Williamsburg
Kniha
Proceedings of NFM'25
Edice
Lecture Notes in Computer Science
ISSN
0302-9743
Periodikum
Číslo
15682
Stát
Spolková republika Německo
Strany od
421
Strany do
440
Strany počet
20
URL
https://link.springer.com/content/pdf/10.1007/978-3-031-93706-4_24.pdf?pdf=inline%20link
Plný text v Digitální knihovně
http://hdl.handle.net/
BibTex
@inproceedings{BUT197713, author="Michal {Šedý} and Lukáš {Holík}", title="Automata Size Reduction by Procedure Finding", booktitle="Proceedings of NFM'25", year="2025", series="Lecture Notes in Computer Science", journal="Lecture Notes in Computer Science", number="15682", pages="421--440", publisher="Springer Nature Switzerland AG", address="Williamsburg", doi="10.1007/978-3-031-93706-4\{_}24", issn="0302-9743", url="https://link.springer.com/content/pdf/10.1007/978-3-031-93706-4_24.pdf?pdf=inline%20link" }