On functions weakly computable by pushdown Petri nets and related systems

zbMATH Open1427.68203arXiv1904.04090MaRDI QIDQ5207052FDOQ5207052

Authors: Jérôme Leroux, M. Praveen, Grégoire Sutre, Philippe Schnoebelen 

Publication date: 3 January 2020

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

Recommendations

• On functions weakly computable by Petri nets and vector addition systems
• On growth function of Petri net
• On boundedness problems for pushdown vector addition systems
• Hyper-Ackermannian bounds for pushdown vector addition systems
• Pushdown automata, multiset automata, and Petri nets

zbMATH Keywords

Petri netspumping lemmafast-growing functionspushdown vector addition systemsweak computation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Semigroups, Presburger formulas, and languages
• The Complexity of the Finite Containment Problem for Petri Nets
• Remarks on blind and partially blind one-way multicounter machines
• Verifying lossy channel systems has nonprimitive recursive complexity.
• Algorithmic analysis of programs with well quasi-ordered domains.
• Complexity hierarchies beyond elementary
• Mixing Lossy and Perfect Fifo Channels
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• Well-structured transition systems everywhere!
• Vector addition system reachability problem, a short self-contained proof
• Reasoning about data repetitions with counter systems
• Process rewrite systems.
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• The equality problem for vector addition systems is undecidable
• Model Checking Multithreaded Programs with Asynchronous Atomic Methods
• Reachability in Petri nets with inhibitor arcs
• The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets
• Decidability of a temporal logic problem for Petri nets
• Analysis of recursively parallel programs
• The power of priority channel systems
• Approximating Petri net reachability along context-free traces
• The reachability problem for Petri nets is not elementary
• On boundedness problems for pushdown vector addition systems
• What makes Petri nets harder to verify: stack or data?
• Nonprimitive recursive complexity and undecidability for Petri net equivalences
• The covering and boundedness problems for branching vector addition systems
• Recursive Petri nets
• Hyper-Ackermannian bounds for pushdown vector addition systems
• On the coverability problem for pushdown vector addition systems in one dimension
• On functions weakly computable by Petri nets and vector addition systems

Cited In (2)

• Unboundedness problems for machines with reversal-bounded counters
• On functions weakly computable by Petri nets and vector addition systems

This page was built for publication: On functions weakly computable by pushdown Petri nets and related systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207052)