GrappaRE -- A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910894632468480 |
|---|---|
| author | De Rosa, Mattia Minas, Mark |
| author_facet | De Rosa, Mattia Minas, Mark |
| contents | A recent paper by Drewes, Hoffmann, and Minas (GCM 2023 proceedings) has shown that certain graph languages can be defined and efficiently recognized by finite automata when strings over typed symbols are interpreted as graphs. This approach has been implemented in the tool GrappaRE, which is described in this paper. GrappaRE allows for the convenient specification of graph languages through regular expressions, converts each of them into a minimized deterministic finite automaton, and checks whether it can recognize graphs without the need for backtracking. Measurements confirm that recognition runs in linear time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_20467 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | GrappaRE -- A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions De Rosa, Mattia Minas, Mark Formal Languages and Automata Theory A recent paper by Drewes, Hoffmann, and Minas (GCM 2023 proceedings) has shown that certain graph languages can be defined and efficiently recognized by finite automata when strings over typed symbols are interpreted as graphs. This approach has been implemented in the tool GrappaRE, which is described in this paper. GrappaRE allows for the convenient specification of graph languages through regular expressions, converts each of them into a minimized deterministic finite automaton, and checks whether it can recognize graphs without the need for backtracking. Measurements confirm that recognition runs in linear time. |
| title | GrappaRE -- A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2503.20467 |