  Extensions to finite-state automata on strings, such as multi-head automata
or multi-counter automata, have been successfully used to encode many
infinite-state non-regular verification problems. In this paper, we consider a
generalization of automata-theoretic infinite-state verification from strings
to labeled series-parallel graphs. We define a model of non-deterministic,
2-way, concurrent automata working on series-parallel graphs and communicating
through shared registers on the nodes of the graph. We consider the following
verification problem: given a family of series-parallel graphs described by a
context-free graph transformation system (GTS), and a concurrent automaton over
series-parallel graphs, is some graph generated by the GTS accepted by the
automaton? The general problem is undecidable already for (one-way) multi-head
automata over strings. We show that a bounded version, where the automata make
a fixed number of reversals along the graph and use a fixed number of shared
registers is decidable, even though there is no bound on the sizes of
series-parallel graphs generated by the GTS. Our decidability result is based
on establishing that the number of context switches is bounded and on an
encoding of the computation of bounded concurrent automata to reduce the
emptiness problem to the emptiness problem for pushdown automata.
