GrappaRE - A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions

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.

Authors

Institutions

Publication Details

Journal
Electronic Proceedings in Theoretical Computer Science
Published
2025-03-25
DOI
https://doi.org/10.4204/eptcs.417.4
Primary Topic
Network Packet Processing and Optimization
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

GrappaRE - A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions

Mark Minas, Mattia De Rosa
Electronic Proceedings in Theoretical Computer Science
Network Packet Processing and Optimization
article

GrappaRE - A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions

Mark Minas, Mattia De Rosa
article en

Abstract

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.

Electronic Proceedings in Theoretical Computer ScienceVol. 417
University of Salerno (IT), Universität der Bundeswehr München (DE)
Openalex Percentile: Top 95%
Network Packet Processing and Optimization
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

GrappaRE - A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions — Mark Minas, Mattia De Rosa · Electronic Proceedings in Theoretical Computer Science (2025) | TGRS Research Map | TGRS