English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This work studies which storage mechanisms in automata permit decidability ofthe emptiness problem. The question is formalized using valence automata, anabstract 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 (typicallyinfinite) monoid $M$ such that valence automata over $M$ are equivalent to(one-way) automata with this type of storage. In fact, many important storagemechanisms can be realized by monoids defined by finite graphs, called graphmonoids. Examples include pushdown stacks, partially blind counters (whichbehave like Petri net places), blind counters (which may attain negativevalues), and combinations thereof.  Hence, we study for which graph monoids the emptiness problem for valenceautomata is decidable. A particular model realized by graph monoids is that ofPetri nets with a pushdown stack. For these, decidability is a long-standingopen question and we do not answer it here.  However, if one excludes subgraphs corresponding to this model, acharacterization can be achieved. Moreover, we provide a description of thosestorage mechanisms for which decidability remains open. This leads to a modelthat naturally generalizes both pushdown Petri nets and the prioritymulticounter machines introduced by Reinhardt.  The cases that are proven decidable constitute a natural and apparently newextension of Petri nets with decidable reachability. It is finally shown thatthis model can be combined with another such extension by Atig and Ganty: Wepresent a further decidability result that subsumes both of these Petri netextensions.

The Emptiness Problem for Valence Automata over Graph Monoids