The ideal view on Rackoff's coverability technique

DOI10.1016/j.ic.2020.104582zbMath1475.68210OpenAlexW4206480932MaRDI QIDQ5925512

Publication date: 13 April 2021

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

Full work available at URL: http://wrap.warwick.ac.uk/135160/1/WRAP-ideal-view-Rackoff%27s-coverability-technique-Lazic-2020.pdf

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Ordinal recursive complexity of unordered data nets
Decidability and complexity of Petri nets with unordered data
Recursivite et cônes rationnels fermés par intersection
Decision problems for propositional linear logic
The covering and boundedness problems for vector addition systems
Algorithmic analysis of programs with well quasi-ordered domains.
The covering and boundedness problems for branching vector addition systems
On Freeze LTL with Ordered Attributes
Complexity Hierarchies beyond Elementary
Expand, Enlarge, and Check for Branching Vector Addition Systems
Alternating Vector Addition Systems with States
Nonelementary Complexities for Branching VASS, MELL, and Extensions
Extending the Rackoff technique to Affine nets
The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets
Multiply-Recursive Upper Bounds with Higman’s Lemma
Forward Analysis for WSTS, Part II: Complete WSTS
Complexity Analysis of the Backward Coverability Algorithm for VASS
On Functions Weakly Computable by Petri Nets and Vector Addition Systems
Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
The Complexity of Coverability in ν-Petri Nets
The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
The complexity of decision procedures in relevance logic II
Handling Infinitely Branching WSTS
Monotonic and Downward Closed Games
The Power of Priority Channel Systems
Well-structured transition systems everywhere!
Fine analysis of the quasi-orderings on the power set

This page was built for publication: The ideal view on Rackoff's coverability technique