  This paper proves the decidability of the emptiness problem for two models
which recognize graphs: graph-walking automata, and tilings of graphs by star
subgraphs (star automata). Furthermore, it is proved that the non-emptiness
problem for graph-walking automata (that is, whether a given automaton accepts
at least one graph) is NEXP-complete. For star automata, which generalize
nondeterministic tree automata to the case of graphs, it is proved that their
non-emptiness problem is NP-complete.
