Result Details
Automata Size Reduction by Procedure Finding
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.
Nondeterministic Finite Automata, Reduction, Regular Expressions, Network
Intrusion Detection Systems
@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"
}Reliable, Secure, and Intelligent Computer Systems, BUT, Vnitřní projekty VUT, FIT-S-23-8151, start: 2023-03-01, end: 2026-02-28, running
Representing Boolean Functions by a Self-Adaptable Data Structure, GACR, Standardní projekty, GA23-07565S, start: 2023-01-01, end: 2025-12-31, running