Detail publikačního výsledku

Automata Size Reduction by Procedure Finding

ŠEDÝ, M.; HOLÍK, L.

Originální název

Automata Size Reduction by Procedure Finding

Anglický název

Automata Size Reduction by Procedure Finding

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

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.

Klíčová slova

Nondeterministic Finite Automata, Reduction, Regular Expressions, Network Intrusion Detection Systems

Klíčová slova v angličtině

Nondeterministic Finite Automata, Reduction, Regular Expressions, Network Intrusion Detection Systems

Autoři

ŠEDÝ, M.; HOLÍK, L.

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

Lecture Notes in Computer Science

Čí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

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