@article{tac-12,
  author    = {Franck Cassez},
  title     = {The Complexity of Codiagnosability for Discrete Event and
               Timed Systems},
  journal   = {IEEE Trans. Automat. Contr.},
  volume    = {57},
  number    = {7},
  year      = {2012},
  type = {A - Journal},
  pages     = {1752-1764},
  urlpaper = {papers/tac-2012.pdf},
  url_link       = {http://dx.doi.org/10.1109/TAC.2012.2183169},
  doi = {http://dx.doi.org/10.1109/TAC.2012.2183169},
  mywebpage = {timed},
  keywords = {timed automata, Fault diagnosis, Complexity},
  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 characterisation of codiagnosability for FA and TA which extends the necessary and sufficient condition that characterises diagosability. 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. We then generalise the previous results to the case of dynamic observers. Finally we show that the codiagnosis problem for TA under bounded resources is 2EXPTIME-complete.
  }
}

{"_id":"sHcnaNs73CoAaJS8Q","bibbaseid":"cassez-thecomplexityofcodiagnosabilityfordiscreteeventandtimedsystems-2012","author_short":["Cassez, F."],"bibdata":{"bibtype":"article","type":"A - Journal","author":[{"firstnames":["Franck"],"propositions":[],"lastnames":["Cassez"],"suffixes":[]}],"title":"The Complexity of Codiagnosability for Discrete Event and Timed Systems","journal":"IEEE Trans. Automat. Contr.","volume":"57","number":"7","year":"2012","pages":"1752-1764","urlpaper":"papers/tac-2012.pdf","url_link":"http://dx.doi.org/10.1109/TAC.2012.2183169","doi":"http://dx.doi.org/10.1109/TAC.2012.2183169","mywebpage":"timed","keywords":"timed automata, Fault diagnosis, Complexity","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 characterisation of codiagnosability for FA and TA which extends the necessary and sufficient condition that characterises diagosability. 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. We then generalise the previous results to the case of dynamic observers. Finally we show that the codiagnosis problem for TA under bounded resources is 2EXPTIME-complete. ","bibtex":"@article{tac-12,\n author = {Franck Cassez},\n title = {The Complexity of Codiagnosability for Discrete Event and\n Timed Systems},\n journal = {IEEE Trans. Automat. Contr.},\n volume = {57},\n number = {7},\n year = {2012},\n type = {A - Journal},\n pages = {1752-1764},\n urlpaper = {papers/tac-2012.pdf},\n url_link = {http://dx.doi.org/10.1109/TAC.2012.2183169},\n doi = {http://dx.doi.org/10.1109/TAC.2012.2183169},\n mywebpage = {timed},\n keywords = {timed automata, Fault diagnosis, Complexity},\n abstract = {\n 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 characterisation of codiagnosability for FA and TA which extends the necessary and sufficient condition that characterises diagosability. 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. We then generalise the previous results to the case of dynamic observers. Finally we show that the codiagnosis problem for TA under bounded resources is 2EXPTIME-complete.\n }\n}\n\n","author_short":["Cassez, F."],"key":"tac-12","id":"tac-12","bibbaseid":"cassez-thecomplexityofcodiagnosabilityfordiscreteeventandtimedsystems-2012","role":"author","urls":{"Paper":"http://science.mq.edu.au/~fcassez/bib/papers/tac-2012.pdf"," link":"http://dx.doi.org/10.1109/TAC.2012.2183169"},"keyword":["timed automata","Fault diagnosis","Complexity"],"metadata":{"authorlinks":{}},"downloads":1,"html":""},"bibtype":"article","biburl":"http://science.mq.edu.au/~fcassez/bib/franck-bib.bib","dataSources":["8742EsvjQfyP2fYBW","qbqYFWskmoonRB43F","yYF8uwWqay28JyxZC"],"keywords":["timed automata","fault diagnosis","complexity"],"search_terms":["complexity","codiagnosability","discrete","event","timed","systems","cassez"],"title":"The Complexity of Codiagnosability for Discrete Event and Timed Systems","year":2012,"downloads":1}