Skip to Main content Skip to Navigation
New interface
Conference papers

Diagnosability of pushdown systems

Christophe Morvan 1 Sophie Pinchinat 2 
2 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Partial observation of discrete-event systems features a setting where events split into observable and unobservable ones. In this context, the diagnosis of a discrete-event system consists in detecting defects from the (partial) observation of its executions. Diagnosability is the property that any defect is eventually detected. Not surprisingly, it is a major issue in practical applications. We investigate diagnosability for classes of pushdown systems: it is undecidable in general, but we exhibit reasonably large classes of visibly pushdown systems where the problem is decidable. For these classes, we furthermore prove the decidability of a stronger property: the bounded latency, which guarantees the existence of a uniform bound on the respond delay after the defect has occurred. We also explore a generalization of the approach to higher-order pushdown systems.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Christophe Morvan Connect in order to contact the contributor
Submitted on : Monday, October 11, 2010 - 5:11:21 PM
Last modification on : Friday, February 4, 2022 - 3:24:32 AM
Long-term archiving on: : Thursday, October 25, 2012 - 4:51:24 PM


Files produced by the author(s)


  • HAL Id : inria-00525397, version 1


Christophe Morvan, Sophie Pinchinat. Diagnosability of pushdown systems. Haifa Verification Conference, Oct 2009, Haifa, Israel. ⟨inria-00525397⟩



Record views


Files downloads