Deciding detectability for labeled Petri nets

0504048 - MÚ 2020 RIV NL eng J - Journal Article
Masopust, Tomáš - Yin, X.
Deciding detectability for labeled Petri nets.
Automatica. Roč. 104, June (2019), s. 238-241. ISSN 0005-1098. E-ISSN 1873-2836
R&D Projects: GA ČR(CZ) GC19-06175J
Institutional support: RVO:67985840
Keywords : discrete event systems * Petri nets * complexity
OECD category: Automation and control systems
Impact factor: 5.541, year: 2019
Method of publishing: Limited access
http://dx.doi.org/10.1016/j.automatica.2019.02.058

Detectability of discrete event systems is a property to decide whether the current and subsequent states can be determined based on observations. We investigate the existence of algorithms for checking strong and weak detectability for systems modeled as labeled Petri nets. Strong detectability requires that we can always determine, after a finite number of observations, the current and subsequent markings of the system, while weak detectability requires that we can determine, after a finite number of observations, the current and subsequent markings for some trajectories of the system. We show that there is an algorithm to check strong detectability requiring exponential space, and that there is no algorithm to check weak detectability.
Permanent Link: http://hdl.handle.net/11104/0295763