TY - JOUR

T1 - State Complexity of Boolean Operations on Graph-Walking Automata

AU - Мартынова, Ольга Максимовна

AU - Охотин, Александр Сергеевич

PY - 2026/9

Y1 - 2026/9

N2 - 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 presented), operating on graphs with k labels of edge end-points, is representable by a GWA with (Formula presented) states, and at least (Formula presented) states are necessary in the worst case. For the intersection, the upper bound is (Formula presented) and the lower bound is (Formula presented). The upper bound for the complementation is (Formula presented), and the lower bound is (Formula presented).

AB - 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 presented), operating on graphs with k labels of edge end-points, is representable by a GWA with (Formula presented) states, and at least (Formula presented) states are necessary in the worst case. For the intersection, the upper bound is (Formula presented) and the lower bound is (Formula presented). The upper bound for the complementation is (Formula presented), and the lower bound is (Formula presented).

KW - Graph-walking automata

KW - complementation

KW - intersection

KW - state complexity

KW - union

UR - https://www.mendeley.com/catalogue/154387c0-1bb2-352d-936a-706598f4dccf/

U2 - 10.1142/s0129054124420012

DO - 10.1142/s0129054124420012

M3 - Article

VL - 37

SP - 723

EP - 743

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 6

ER -