On functions weakly computable by pushdown Petri nets and related systems

MaRDI QIDQ5207052zbMATH OpenFDO

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

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)

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

Cites work

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

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)