The complexity of codiagnosability for discrete event and timed systems

Franck Cassez*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

4 Citations (Scopus)

Abstract

In this paper we study the fault codiagnosis problem for discrete event systems given by finite automata (FA) and timed systems given by timed automata (TA). We provide a uniform characterization of codiagnosability for FA and TA which extends the necessary and sufficient condition that characterizes diagnosability. We also settle the complexity of the codiagnosability problems both for FA and TA and show that codiagnosability is PSPACE-complete in both cases. For FA this improves on the previously known bound (EXPTIME) and for TA it is a new result. Finally we address the codiagnosis problem for TA under bounded resources and show it is 2EXPTIME-complete.

Original languageEnglish
Title of host publicationAutomated Technology for Verification and Analysis
Subtitle of host publication8th International Symposium, ATVA 2010 Singapore, September 21-24, 2010 Proceedings
EditorsAhmed Bouajjani, Wei-Ngan Chin
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages82-96
Number of pages15
ISBN (Print)3642156428, 9783642156427
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event8th International Symposium on Automated Technology for Verification and Analysis, ATVA 2010 - Singapore, Singapore
Duration: 21 Sep 201024 Sep 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6252
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Symposium on Automated Technology for Verification and Analysis, ATVA 2010
CountrySingapore
CitySingapore
Period21/09/1024/09/10

Fingerprint Dive into the research topics of 'The complexity of codiagnosability for discrete event and timed systems'. Together they form a unique fingerprint.

Cite this