Umeå universitets logga

In many application areas, it is necessary to specify and check  properties of graphs.  Such properties may be complex, placing structural requirements on graph regions of unbounded size. In this paper, we show that alternating graph automata can check such graph properties, e.g., whether a given input graph is a tree, or whether  it contains a Hamiltonian cycle or not.  In fact, we show that these automata can accept PSPACE-complete graph languages and that, conversely, their uniform membership  problem is contained in PSPACE.