Skip to main content

TS

A topological perspective on diagnosis

Authors

Andreas Bauer and Sophie Pinchinat

NICTA

Irisa

Abstract

We propose a topological perspective on the diag- nosis problem for discrete-event systems. In an infinitary framework, we argue that the construction of a centralized diagnoser is conditioned by two fundamental properties: saturation and openness. We show that these properties are decidable for ω- regular languages. Usually, openness is guaranteed implicitly in practical settings. In contrast to this, we prove that the saturation problem is PSPACE-complete, which is relevant for the overall complexity of diagnosis.

BibTeX Entry

  @inproceedings{Bauer_Pinchinat_08,
    publisher        = {IEEE Computer Society},
    author           = {Bauer, Andreas and Pinchinat, Sophie},
    month            = may,
    editor           = {{Bengt Lennartson, Martin Fabian, Knut Åkesson, Alessandro Giua, Ratnesh Kumar}},
    year             = {2008},
    title            = {A Topological Perspective on Diagnosis},
    booktitle        = {9th International Workshop on Discrete Event Systems (WODES)},
    pages            = {218-224},
    address          = {Göteborg, Sweden}
  }

Download

Served by Apache on Linux on seL4.