  We consider recognizable trace rewriting systems with level-regular contexts
(RTL). A trace language is level-regular if the set of Foata normal forms of
its elements is regular. We prove that the rewriting graph of a RTL is
word-automatic. Thus its first-order theory is decidable. Then, we prove that
the concurrent unfolding of a finite concurrent automaton with the reachability
relation is a RTL graph. It follows that the first-order theory with the
reachability predicate (FO[Reach] theory) of such an unfolding is decidable. It
is known that this property holds also for the ground term rewriting graphs. We
provide examples of finite concurrent automata of which the concurrent
unfoldings fail to be ground term rewriting graphs. The infinite grid tree (for
each vertex of an infinite grid, there is an edge from this vertex to the
origin of a copy of the infinite grid) is such an unfolding. We prove that the
infinite grid tree is not a ground term rewriting graph. We have thus obtained
a new class of graphs for with a decidable FO[Reach] theory.
