Skip to main content


A topological perspective on diagnosis


Andreas Bauer and Sophie Pinchinat




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

    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}


Served by Apache on Linux on seL4.