The emptiness problem for valence automata over graph monoids

DOI10.1016/j.ic.2020.104583zbMath1475.68170arXiv1710.07528OpenAlexW3014120279MaRDI QIDQ2662504

Georg Zetzsche

Publication date: 13 April 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.07528

zbMATH Keywords

Petri netmonoidreachability problememptiness problemvector addition systempushdowncounterstorage mechanism

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (3)

Recent advances on reachability problems for valence systems (invited talk) ⋮ Unboundedness Problems for Languages of Vector Addition Systems. ⋮ Bounded Context Switching for Valence Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the rational subset problem for groups.
• The submonoid and rational subset membership problems for graph groups.
• Sequential grammars and automata with valences
• The emptiness problem for valence automata or: another decidable extension of Petri nets
• What makes some language theory problems undecidable
• Principal AFL
• Semilinearity and Context-Freeness of Languages Accepted by Valence Automata
• Computing Downward Closures for Stacked Counter Automata
• The rational subset membership problem for groups: a survey
• On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
• Formal Languages and Groups as Memory
• Characterizations of the decidability of some problems for regular trace languages
• Reachability in Petri Nets with Inhibitor Arcs
• Silent Transitions in Automata with Storage
• A Note on "The Comparability Graph of a Tree"
• On the index of a context-free grammar and language

This page was built for publication: The emptiness problem for valence automata over graph monoids