Recent Advances on Reachability Problems for Valence Systems (Invited Talk)
Lecture notes in computer science2021pp. 52–65
Citations Over TimeTop 20% of 2021 papers
Abstract
Abstract Valence systems are an abstract model of computation that consists of a finite-state control and some storage mechanism. In contrast to traditional models, the storage mechanism is not fixed, but given as a parameter. This allows us to precisely state questions like: For which storage mechanisms is the reachability problem decidable? This survey reports on recent results that aim to understand the impact of the storage mechanism on decidability and complexity of several variants of the reachability problem. The considered problems are configuration reachability, model-checking first-order logic with reachability, and reachability under bounded context switching and scope-boundedness.
Related Papers
- → Decidability of reachability in vector addition systems (Preliminary Version)(1982)319 cited
- → Some decidable results on reachability of solvable systems(2013)5 cited
- → Structural liveness of Petri nets is ExpSpace-hard and decidable(2019)5 cited
- → Delta-Complete Analysis for Bounded Reachability of Hybrid Systems(2014)5 cited
- → An approach to cyclic protocol validation(1996)4 cited