Diagnosis and Opacity Problems for Infinite State Systems Modeled by Recursive Tile Systems - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Discrete Event Dynamic Systems Year : 2015

Diagnosis and Opacity Problems for Infinite State Systems Modeled by Recursive Tile Systems

Abstract

The analysis of discrete event systems under partial observation is an important topic, with major applications such as the detection of information flow and the diagnosis of faulty behaviors. These questions have, mostly, not been addressed for classical models of recursive systems, such as pushdown systems and recursive state machines. In this paper, we consider recursive tile systems, which are recursive infinite systems generated by a finite collection of finite tiles, a simplified variant of deterministic graph grammars (slightly more general than pushdown systems). Since these systems are infinite-state in general powerset constructions for monitoring do not always apply. We exhibit computable conditions on recursive tile systems and present non-trivial constructions that yield effective computation of the monitors.We apply these results to the classic problems of state-based opacity and diagnosability (off-line verification of opacity and diagnosability, and also run-time monitoring of these properties). For a decidable subclass of recursive tile systems, we also establish the decidability of the problems of state-based opacity and diagnosability.
Fichier principal
Vignette du fichier
jdeds-rts14.pdf (251.08 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00994970 , version 1 (22-05-2014)

Identifiers

Cite

Sébastien Chédor, Christophe Morvan, Sophie Pinchinat, Hervé Marchand. Diagnosis and Opacity Problems for Infinite State Systems Modeled by Recursive Tile Systems. Discrete Event Dynamic Systems, 2015, 25 ((1-2)), pp.271-294. ⟨10.1007/s10626-014-0197-3⟩. ⟨hal-00994970⟩
198 View
194 Download

Altmetric

Share

Gmail Facebook X LinkedIn More