Systems of Graph Formulas and their Equivalence to Alternating Graph Automata
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_ | 1866915745636548608 |
|---|---|
| author | Drewes, Frank Hoffmann, Berthold Minas, Mark |
| author_facet | Drewes, Frank Hoffmann, Berthold Minas, Mark |
| contents | Graph-based modeling plays a fundamental role in many areas of computer science. In this paper, we introduce systems of graph formulas with variables for specifying graph properties; this notion generalizes the graph formulas introduced in earlier work by incorporating recursion. We show that these formula systems have the same expressive power as alternating graph automata, a computational model that extends traditional finite-state automata to graphs, and allows both existential and universal states. In particular, we provide a bidirectional translation between formula systems and alternating graph automata, proving their equivalence in specifying graph languages. This result implies that alternating graph automata can be naturally represented using logic-based formulations, thus bridging the gap between automata-theoretic and logic-based approaches to graph language specification. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25260 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Systems of Graph Formulas and their Equivalence to Alternating Graph Automata Drewes, Frank Hoffmann, Berthold Minas, Mark Formal Languages and Automata Theory Graph-based modeling plays a fundamental role in many areas of computer science. In this paper, we introduce systems of graph formulas with variables for specifying graph properties; this notion generalizes the graph formulas introduced in earlier work by incorporating recursion. We show that these formula systems have the same expressive power as alternating graph automata, a computational model that extends traditional finite-state automata to graphs, and allows both existential and universal states. In particular, we provide a bidirectional translation between formula systems and alternating graph automata, proving their equivalence in specifying graph languages. This result implies that alternating graph automata can be naturally represented using logic-based formulations, thus bridging the gap between automata-theoretic and logic-based approaches to graph language specification. |
| title | Systems of Graph Formulas and their Equivalence to Alternating Graph Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2510.25260 |