Reachability problem

The reachability problem refers to the task of determining whether a specific state or marking is reachable within a system, typically modeled using Petri nets. It is a fundamental concept in the study of dynamic properties of a system and involves finding if a given marking is in the reachability set. Solving the reachability problem allows for the identification of reachable markings and the detection of deadlocks within the system.From: System Modeling and Control with Resource-Oriented Petri Nets [2019], From strong to exact Petri net computers [2022]

Petri Nets

View Chapter

Purchase Book

Published in Richard L. Shell, Ernest L. Hall, Handbook of Industrial Automation, 2000

Frank S. Cheng

Since Theorem 1 is rarely satisfied in most Petri net applications, the reachability problem becomes more important. For the case of reachability, the rank of incidence matrix A is r, where r < n.

Colored Petri nets-based control and experimental validation on three-tank system level control

View Article

Journal Information

Published in International Journal of General Systems, 2023

Marius Brezovan, Radu-Emil Precup, Dan Selişteanu, Liana Stănescu

The other class consists of the feedback control for events methods, which are derived from Ramadge and Wonham theory of supervisory control, and the corresponding Petri net models are called labeled Petri nets. Some methods in this class are reported in H.-S. Wang (1993), Giua and Di Cesare (1995), and Giua (2013). The controllability problem dedicated to Petri net languages is proved in Kumar and Holloway (1992) to be reducible to the reachability problem of Petri nets.

From strong to exact Petri net computers

View Article

Journal Information

Published in International Journal of Parallel, Emergent and Distributed Systems, 2022

Dmitry A. Zaitsev, MengChu Zhou

A construct [1], presented by Lipton, proves that the Petri net reachability problem has exponential space complexity. More precise estimation for the Petri net reachability tree size is in demand for ongoing research as well [2,3]. The constructs similar to described by Lipton are recently employed in Petri net computers [4], universal Petri nets [5,6], and in transformations of Petri nets to concurrent programs [7].

Reachability problem

Explore chapters and articles related to this topic

Petri Nets

Colored Petri nets-based control and experimental validation on three-tank system level control

From strong to exact Petri net computers