Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.20227 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910876398780416 |
|---|---|
| author | Šedý, Michal Holík, Lukáš |
| author_facet | Šedý, Michal Holík, Lukáš |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20227 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Automata Size Reduction by Procedure Finding Šedý, Michal Holík, Lukáš Formal Languages and Automata Theory Networking and Internet Architecture 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. |
| title | Automata Size Reduction by Procedure Finding |
| topic | Formal Languages and Automata Theory Networking and Internet Architecture |
| url | https://arxiv.org/abs/2410.20227 |