Diagnosis 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 : Diagnosis problems of discrete-event systems consist in detecting unobservable defects during system execution. For finite-state systems, the theory is well understood and a number of effective solutions have been developed. For infinite-state systems, however, there are only few results, mostly identifying classes where the problem is undecidable. We consider higher-order pushdown systems and investigate two basic variants of diagnosis problems: the diagnosability, which consists in deciding whether defects can be detected within a finite delay, and the bounded-latency problem, which consists in determining a bound for the delay of detecting defects. We establish that the diagnosability problem is decidable for arbitrary sub-classes of higher-order visibly pushdown systems provided unobservable events leave the stacks unchanged. For this case, we present an effective algorithm. Otherwise, we show that diagnosability becomes undecidable already for first-order visibly pushdown automata. Furthermore, we establish that the bounded-latency problem for higher-order pushdown systems is as hard as deciding finiteness of a higher-order pushdown language. This is in contrast with the case of finite-state systems where the problem reduces to diagnosability.
Type de document :
Rapport
[Research Report] PI 1904, 2008, pp.19
Liste complète des métadonnées

https://hal.inria.fr/inria-00337614
Contributeur : Anne Jaigu <>
Soumis le : vendredi 7 novembre 2008 - 14:46:48
Dernière modification le : mercredi 16 mai 2018 - 11:23:04
Document(s) archivé(s) le : lundi 7 juin 2010 - 20:32:59

Fichiers

PI-1904.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00337614, version 1

Citation

Christophe Morvan, Sophie Pinchinat. Diagnosis of Pushdown Systems. [Research Report] PI 1904, 2008, pp.19. 〈inria-00337614〉

Partager

Métriques

Consultations de la notice

279

Téléchargements de fichiers

117