State Complexity of Boolean Operations on Graph-Walking Automata
Olga Martynova, Alexander Okhotin · International Journal of Foundations of Computer Science · 2024
Finite automata that traverse graphs by moving along their edges are known as graph-walking automata (GWA). This paper investigates the state complexity of Boolean operations for this model. It is proved that the union of GWA with m and n states, with [Formula: see text], operating on graphs with k labels of edge end-points, is representable by a GWA with [Formula: see text] states, and at least [Formula: see text] states are necessary in the worst case. For the intersection, the upper bound is [Formula: see text] and the lower bound is [Formula: see text]. The upper bound for the complementation is [Formula: see text], and the lower bound is [Formula: see text].