Title: The Emptiness Problem for Valence Automata over Graph Monoids,
Abstract: This work studies which storage mechanisms in automata permit decidability of
the emptiness problem. The question is formalized using valence automata, an
abstract model of automata in which the storage mechanism is given by a monoid.
For each of a variety of storage mechanisms, one can choose a (typically
infinite) monoid $M$ such that valence automata over $M$ are equivalent to
(one-way) automata with this type of storage. In fact, many important storage
mechanisms can be realized by monoids defined by finite graphs, called graph
monoids. Examples include pushdown stacks, partially blind counters (which
behave like Petri net places), blind counters (which may attain negative
values), and combinations thereof.
Hence, we study for which graph monoids the emptiness problem for valence
automata is decidable. A particular model realized by graph monoids is that of
Petri nets with a pushdown stack. For these, decidability is a long-standing
open question and we do not answer it here.
However, if one excludes subgraphs corresponding to this model, a
characterization can be achieved. Moreover, we provide a description of those
storage mechanisms for which decidability remains open. This leads to a model
that naturally generalizes both pushdown Petri nets and the priority
multicounter machines introduced by Reinhardt.
The cases that are proven decidable constitute a natural and apparently new
extension of Petri nets with decidable reachability. It is finally shown that
this model can be combined with another such extension by Atig and Ganty: We
present a further decidability result that subsumes both of these Petri net
extensions.