Parsing Hypergraphs using Context-Free Positional Grammars
Gennaro Costagliola, Federico Vastarini · 2026
Read Parsing Hypergraphs using Context-Free Positional Grammars by Gennaro Costagliola, Federico Vastarini (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-03896.txt.
Description
Gennaro Costagliola and Federico Vastarini present work in progress on parsing hypergraphs, deciding whether a given hypergraph belongs to a language a grammar can make. Their grammars are context-free hyperedge swap grammars, which build hypergraphs by swapping hyperedges for subgraphs. The approach rests on a new LR parsing technique for positional grammars, also under development.
The central move is a reduction from hyperedge swapping to positional grammars with extra structural limits, using permutation-based steps to find the right order of hyperedges in each rule. Early results also separate two kinds of ambiguity, in generating graphs versus recognizing them. Which swap languages the method can parse is still under study. Graph parsing underlies tools from program analysis to chemistry, so new parsing routes have wide potential reach.
Catalog record
| CREATOR | Gennaro Costagliola, Federico Vastarini |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-03896