2025/10/29 by Drewes, Frank, Hoffmann, Berthold, Minas, Mark
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2510.25260
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.