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.
Type de document :
Communication dans un congrès
Kedar Namjoshi and Andreas Zeller. Haifa Verification Conference, Oct 2009, Haifa, Israel. Springer, 6405, 2009, LNCS
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00525397
Contributeur : Christophe Morvan <>
Soumis le : lundi 11 octobre 2010 - 17:11:21
Dernière modification le : vendredi 16 novembre 2018 - 01:23:39
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 16:51:24

Fichier

hvc09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00525397, version 1

Citation

Christophe Morvan, Sophie Pinchinat. Diagnosability of pushdown systems. Kedar Namjoshi and Andreas Zeller. Haifa Verification Conference, Oct 2009, Haifa, Israel. Springer, 6405, 2009, LNCS. 〈inria-00525397〉

Partager

Métriques

Consultations de la notice

269

Téléchargements de fichiers

120