# Archived/Old Publications

## Presentations

### " A Distributed Algorithm for On-Line Diagnosis of Place-Bordered Petri Nets "

- by S. Genc and S. Lafortune
- Presented at the
*IFAC World Congress* - Praha, Czech Republic, July, 04-08, 2005
- [PDF]

### " Active Acquisition of Information for Diagnosis of Discrete-Event Systems "

- by David Thorsley and Demosthenis Teneketzis
- Presented at the
*Allerton Conferences* - Urbana-champaign, IL, USA, September, 29-30, 2004
- [PDF]

### " The Control and Verification Of Similar Agents Operating In A Broadcast Network Environment "

- by K. Rohloff and S. Lafortune
- Presented at the
*IEEE Conf. on Decision and Control* - Maui , Hawaii , December, 9-12, 2003
- [PDF]

### " Supervisor Existence For Modular Discrete-Event Systems "

- by K. Rohloff and S. Lafortune
- Presented at the
*IFAC Conference on Control Systems Design* - Bratislava, Slovak Republic , September, 7-10, 2003
- [PDF]

### " Failure Diagnosis of Stochastic Automata "

- by David Thorsley and Demosthenis Teneketzis
- Presented at the
*International Conf. on Principles of Diagnosis* - Washington, DC, USA, June, 12-14, 2003
- [PDF]

### " Distributed Diagnosis Of Discrete-Event Systems Using Petri Nets "

- by Sahika Genc and Stephane Lafortune
- Presented at the
*International Conf. of Application and Theory of Petri Nets* - Eindhoven , The Netherlands , June, 23-27, 2003
- [PDF]

### " Failure Diagnosis Of Discrete Event Systems: The Case Of Intermittent Faults "

- by O. Contant, S. Lafortune, and D. Teneketzis
- Presented at the
*IEEE Conf. on Decision and Control* - Las Vegas , NV , December, 10-13, 2002
- [PDF]

### " On The Computational Complexity Of Verification Of Modular Discrete-Event Systems "

- by K. Rohloff and S. Lafortune
- Presented at the
*IEEE Conf. on Decision and Control* - Las Vegas , NV , December, 10-13, 2002
- [PDF]

### " UMDES-LIB, Library of Commands for Discrete Event Systems Modeled By Finite State Machines "

- by Discrete Event Systems Group At University of Michigan Under the Coordination of Stephane Lafortune and Demosthenis Teneketzis
- Presented at the
*International Workshop on Discrete Event Systems* - Ghent, Belgium, August, 21-23, 2000
- [PDF]

### " A General Architecture For Decentralized Supervisory Control Of Discrete-Event Systems "

- by T. Yoo and S. Lafortune
*Presented at the*International Workshop on Discrete Event Systems- Ghent , Belgium , August, 21-23, 2000
- [PDF]

## Conferences

### " Predictability In Discrete-Event Systems Under Partial Observation "

*This paper studies the problem of predicting occurrences of a significant event in a discrete-event system. The predictability of occurrences of an event in a system is defined in the context of formal languages. The predictability of a language is a stronger condition than the diagnosability of the language. An implementable necessary and sufficient condition for predictability of occurrences of an event in systems modeled by regular languages is presented.*

- by S. Genc and S. Lafortune
- Presented at the
*IFAC Symposium on Fault Detection, Supervision and Safety of Technical Processes* - Beijing, China, August, 30-31, 2006
- [PDF]

### " DESUMA: A Tool Integrating GIDDES and UMDES "

*The key features of the software tool DESUMA for the study of discrete event systems modeled by finite-state automata are highlighted. DESUMA is the tool resulting from the integration of the UMDES library of routines for the study of discrete event systems (developed at the University of Michigan) within the graphical environment for visualizing discrete event systems (developed at Mount Allison University).*

- by L. Ricker, S. Lafortune and S. Genc
- Presented at the
*8th International Workshop on Discrete-Event Systems* - Ann Arbor, MI, USA, July, 10-12, 2006
- [PDF]

### " Testing Modularity of Local Supervisors: An Approach Based On Abstractions "

*This paper presents an efficient way to detect conflict in composed systems controlled by local supervisors designed using the Supervisory Control Theory of discrete event systems. The idea is to apply the required modularity test not over the languages implemented by the supervisors, but over abstractions of the supervisors with some specific characteristics. The concept of observer and some constraints on the set of relevant events are the basis for the approach. An illustrative example is presented.*

- by P.N. Pena, J.E.R. Cury and S. Lafortune
- Presented at the
*International Workshop on Discrete Event Systems - WODES'06* - Ann Arbor, US, July, 10-12, 2006
- [PDF]

### " Diagnosis of Cyclic Discrete-Event Systems Using Active Acquisition of Information "

*This paper extends the active acquisition of information approach developed in [1] from the case of acyclic, timed automata to the more general case of cyclic, asynchronous automata. Conditions for the existence of optimal solutions at finite cost are presented for both logical and stochastic systems. The information state method developed in the previous paper is reduced to a “diagnoser state” method wherein actions are computed for each potential set of states, as opposed to each potential set of strings. After developing a method of finding an optimal policy, a limited lookahead algorithm is presented to produce a suboptimal solution with less intensive computation.*

- by David Thorsley and Demosthenis Teneketzis
- Presented at the
*8th International Workshop on Discrete Event Systems (WODES '06)* - Ann Arbor, USA, July, 10-12, 2006
- [PDF]

### " Decentralized Diagnosis of Discrete Event Systems Using Unconditional and Conditional Decisions "

*The past decade has witnessed the development of a body of theory, with associated applications, for fault diagnosis of dynamic systems that can be modeled in a discrete event systems framework. This paper first discusses the dual problem of diagnosing the absence of faults in centralized and decentralized settings. The paper then develops new definitions of decentralized diagnosis in the context of a general decentralized architecture that allows for the use of “conditional decisions” by local diagnosers. The properties of these new definitions of decentralized diagnosability are presented and their relationship with existing work discussed. Corresponding verification algorithms are also described.*

- by Yin Wang, Stéphane Lafortune, Tae-Sic Yoo
- Presented at the
*Proceedings of the 44th IEEE Conference on Decision and Control* - Sevilla, Spain, December, 12-15, 2005
- [PDF]

### " A Distributed Algorithm for On-Line Diagnosis of Place-Bordered Petri Nets "

*A new distributed algorithm for on-line fault detection and isolation of discrete-event systems modeled by Petri nets is presented. The algorithm is applicable to systems modeled in a modular manner by means of place-bordered Petri nets, i.e., Petri nets with common places but distinct transitions. These Petri nets have transition labeled with events; fault events are modeled as transitions labeled with unobservable events. It is assumed that the diagnoser modules are able to communicate in real-time during the diagnostic process. A merge function is defined to combine the individual diagnoser states and recover the complete diagnoser state that would be obtained under a monolithic approach.*

- by S. Genc and S. Lafortune
- Presented at the
*IFAC World Congress* - Prague, Czech Republic, July, 04-08, 2005
- [PDF]

### " New Results On Decentralized Diagnosis of Discrete Event Systems "

*The past decade has witnessed the development of a body of theory, with associated applications, for fault diagnosis of dynamic systems that can be modeled in a discrete event systems framework. This paper presents several new notions of diagnosability, together with on-line diagnosis decision rules, in the context of a general decentral-ized architecture that allows for the use of “conditional decisions” by local diagnos-ers. The properties of these new notions of diagnosability are presented and their re-lationship with existing work discussed. Verification algorithms and local diagnoser synthesis methods are briefly outlined.*

- by Y. Wang, T. Yoo and S. Lafortune
- Presented at the
*Allerton Conferences* - Urbana-champaign, IL, USA, September, 29-30, 2004
- [PDF]

### " Active Acquisition of Information for Diagnosis of Discrete-Event Systems "

*A method for determining minimum cost observation strategies for failure diagnosis of discrete event systems is proposed. This “active acquisition” of information method is described for both logical and stochastic discrete event systems.*

- by David Thorsley and Demosthenis Teneketzis
- Presented at the
*Allerton Conferences* - Urbana-champaign, IL, USA, September, 29-30, 2004
- [PDF]

### " The Control and Verification Of Similar Agents Operating In A Broadcast Network Environment "

*We explore issues related to the control and verification of similar agents that interact through events broadcast over a network. The similar agents are modeled as discrete-event systems that have identical structure. System events are partitioned into global and private events that respectively affect all agents or exactly one agent. We show how the state explosion problem inherent to many concurrent systems is not as problematic in this setting. We give a procedure to test if these systems are globally deadlock-free or nonblocking. We explore control and verification problems related to both local and global specifications on these systems. For each module there is exactly one controller and all controllers enforce the same control policy. Necessary and sufficient conditions for achieving local and global specifications in this setting are identified.*

- by K. Rohloff and S. Lafortune
- Presented at the
*IEEE Conf. on Decision and Control* - Maui , Hawaii , December, 9-12, 2003
- [PDF]

### " Supervisor Existence For Modular Discrete-Event Systems "

*This paper examines decision problems involving supervisors for modular systems. We investigate the problem of deciding if there exists a supervisor that can augment a modular system to satisfy a modular global specification. Our system and specification modules are ``discrete-event systems* modeled as finite-state automata. The parallel composition operation is used to model the interaction between the various modules. A supervisor for a discrete-event system observes events as they occur in the system and enforces a control action by disabling some controllable events. We find that these types of problems are generally PSPACE-complete for a large class of systems and specifications.

- by K. Rohloff and S. Lafortune
- Presented at the
*IFAC Conference on Control Systems Design* - Bratislava , Slovak Republic , September, 7-10, 2003
- [PDF]

### " Failure Diagnosis of Stochastic Automata "

*This paper extends the methodology of (Sampath et al., 1995) initially developed for logical finite-state machines to stochastic automata. Using probabilistic information, two notions of diagnosability weaker than tha of Sampath et al. are defined, and a stochastic analogue of the logical diagnoser is constructed. The stochastic diagnoser is used to (i) specify off-line conditions sufficient to guarantee our notions of diagnosability; and (ii) determine how to perform on-line diagnosis of failure events.*

- by David Thorsley and Demosthenis Teneketzis
- Presented at the
*International Conf. on Principles of Diagnosis* - Washington, DC, USA, June, 12-14, 2003
- [PDF]

### " Recent Results On Computational Issues In Supervisory Control "

*We present and discuss the implications of recent results by several researchers on computational issues in supervisory control of discrete event systems. The first issue discussed is the boundary between decidability and undecidability in centralized and decentralized control problems for systems modeled by finite-state automata and subject to regular language specifications. The second issue discussed is the PSPACE-completeness of a large class of verification and control problems for decentralized and modular systems modeled by sets of interacting finite-state automata coupled by parallel composition. The state space explosion inherent to modular systems and the possible time-space tradeoff that arises for computations on these systems are discussed.*

- by K. Rohloff and S. Lafortune
- Presented at the
*International Conf. of Application and Theory of Petri Nets* - Eindhoven , The Netherlands , June, 23-27, 2003
- [PDF]

### " Distributed Diagnosis Of Discrete-Event Systems Using Petri Nets "

*The problem of detecting and isolating fault events in dynamic systems modeled as discrete-event systems is considered. The modeling formalism adopted is that of Petri nets with labeled transitions, where some of the transitions are labeled by different types of unobservable fault events. The Diagnoser Approach for discrete-event systems modeled by automata developed in earlier work is adapted and extended to on-line fault diagnosis of systems modeled by Petri nets, resulting in a centralized diagnosis algorithm based on the notion of *Petri net diagnosers*. A distributed version of this centralized algorithm is also presented. This distributed version assumes that the Petri net model of the system can be decomposed into two place-bordered Petri nets satisfying certain conditions and that the two resulting Petri net diagnosers can exchange messages upon the occurrence of observable events. It is shown that this distributed algorithm is correct in the sense that it recovers the same diagnostic information as the centralized algorithm. The distributed algorithm provides an approach for tackling fault diagnosis of large complex systems.*

- by S. Genc and S. Lafortune
- Presented at the
*International Conf. of Application and Theory of Petri Nets* - Eindhoven, The Netherlands, June, 23-27, 2003
- [PDF]

### " Failure Diagnosis Of Discrete Event Systems: The Case Of Intermittent Faults "

*The diagnosis of “intermittent” faults in dynamic systems modeled as discrete event systems is considered. In many systems, faulty behavior often occurs intermittently, with fault events followed by corresponding “reset” events for these faults, followed by new occurrences of fault events, and so forth. Since these events are usually unobservable, it is necessary to develop diagnostic methodologies for intermittent faults. This paper addresses this issue by: (i) proposing a modeling methodology for discrete event systems with intermittent faults; (ii) introducing new notions of diagnosability associated with fault and reset events; and (iii) developing necessary and sufficient conditions, in terms of the system model and the set of observable events, for these notions of diagnosability. The associated necessary and sufficient conditions are based upon the technique of “diagnosers” introduced in earlier work, albeit the structure of the diagnosers needs to be enhanced to capture the dynamic nature of faults in the system model. The diagnosability conditions are verifiable in polynomial time in the number of states of the diagnosers.*

- by O. Contant, S. Lafortune, and D. Teneketzis
- Presented at the
*IEEE Conf. on Decision and Control* - Las Vegas , NV , December, 10-13, 2002
- [PDF]

### " On The Computational Complexity Of Verification Of Modular Discrete-Event Systems "

*This paper investigates issues related to the computational complexity of automata intersection problems. For several classes of problems, comparing the behavior of sets of interacting finite automata is found to be PSPACE-complete, even in the case of automata accepting prefix-closed languages (equivalently, even when all states are marked). This paper uses these results to investigate the computational complexity of problems related to the verification of supervisory controllers for modular discrete-event systems. Modular discrete-event systems are sets of finite automata combined by the parallel composition operation. We find that a large number of modular discrete-event system verification problems are also PSPACE-complete, even for prefix-closed cases. These results suggest that while system decomposition by parallel composition could lead to significant space savings, it may not lead to sufficient time savings that would aid in the study of "large scale" systems.*

- by K. Rohloff and S. Lafortune
- Presented at the
*IEEE Conf. on Decision and Control* - Las Vegas , NV , December, 10-13, 2002
- [PDF]

### " On The Computational Complexity Of Some Problems Arising In Partially-observed Discrete-Event Systems "

*We study some problems arising in partially-observed discrete-event systems and examine the computational effort required for their solution. First, the problem of verifying the property of diagnosability is considered. In current works, the verification of diagnosability relies on the construction of the diagnoser, a step that requires exponential time in the worst case. We present a new polynomial time algorithm for deciding diagnosability. We also consider the problem of finding an observable event set with minimum cardinality with respect to three properties: diagnosability, normality, and observability. We prove that these search problems are computationally hard by showing that the corresponding decision problems are NP-complete.*

- by T. Yoo and S. Lafortune
- Presented at the
*American Control Conference* - Arlington , Virginia , June, 25-27, 2001
- [PDF]

### " New Results On Decentralized Supervisory Control Of Discrete-Event Systems "

*We present new results on decentralized supervisory control of discrete-event systems. We generalize the control architecture by allowing combinations of ``fusion by intersection* and ``fusion by union* for the control actions issued by the individual (local) supervisors. The algebraic properties of co-observability in the context of this general architecture are presented. We show that appropriate combinations of fusion rules with corresponding decoupled local decision rules guarantee the safety of the closed-loop behavior with respect to a given specification that is not co-observable. We characterize an ``optimal* combination of fusion rules among those combinations guaranteeing the safety of the closed-loop behavior. In addition, a simple supervisor synthesis technique generating the infimal prefix-closed controllable and co-observable superlanguage is presented.

- by T. Yoo and S. Lafortune
- Presented at the
*IEEE Conf. on Decision and Control* - Sydney , Australia , December, 12-15, 2000
- [PDF]

### " On The Effect Of Communication Delays In Failure Diagnosis Of Decentralized Discrete Event Systems "

*We study the eff ect of communication delays on the performance of a coordinated decentralized architecture for failure diagnosis of untimed discrete event systems. The architecture consists of local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. A protocol that realizes the architecture is de ned by the diagnostic information generated at the local sites, the communication rules used by the local sites, and the decision rule used by the coordinator to infer the occurrence of failures. Our prior work [6] has addressed the performance of a set of protocols under the assumption that messages sent from various local sites to the coordinator are received in the order in which they are sent globally. In this work we relax the abovementioned assumption. We modify the coordinator's decision rule for one of the protocols analyzed in [6] to account for the reception of out of order messages at the coordinator's site. We discover conditions on the system structure under which the modi ed protocol performs as well as the centralized diagnostic scheme proposed in [11].*

- by R. Debouk, S. Lafortune, and D. Teneketzis
- Presented at the
*IEEE Conf. on Decision and Control* - Sydney , Australia , December, 12-15, 2000
- [PDF]

### " A General Architecture For Decentralized Supervisory Control Of Discrete-Event Systems "

*We consider a generalized form of the conventional decentralized control architecture for discrete-event systems where the control actions of a set of supervisors can be ``fused* using both union and intersection of enabled events. Namely, the supervisors agree a priori on choosing ``fusion by union* for certain controllable events and ``fusion by intersection* for certain other controllable events. We show that under this generalized architecture, a larger class of languages can be achieved than before since a relaxed version of the notion of co-observability appears in the necessary and sufficient conditions for the existence of supervisors. The computational complexity of verifying these new necessary and sufficient conditions is studied. Finally, a method of partitioning the controllable events between ``fusion by union* and ``fusion by intersection* is presented.

- by T. Yoo and S. Lafortune
- Presented at the
*International Workshop on Discrete Event Systems* - Ghent , Belgium , August, 21-23, 2000
- [PDF]

### " On An Optimization Problem In Sensor Selection "

*We address the following sensor selection problem. We assume that a dynamic system possesses a certain property, call it "Property D," when a set Γ of sensors is used. There is a cost c _{A} associated with each set A of sensors that is a subset of Γ. Given any set of sensors that is a subset of Γ,it is possible to determine, via a test, whether the resulting system-sensor combination possesses Property D. Each test required to check whether or not Property D holds incurs a fixed cost. For each set of sensors A that is a subset of Γ there is an "a priori" probabilty p_{A} that the test will be positive, i.e., a sequence of tests, to minimize the expected cost, associated with the tests, that is incurred until a least expensive combination of sensors that results in a system-sensor combination possessing Property D is identified. We determine conditions on the sensor costs c_{A} and the "a priori" probabilities p_{A} under which the strategy that tests the combinations of sensors in increasing order of cost is optimal with respect to the aforementioned objective.*

- by R. Debouk, S. Lafortune, and D. Teneketzis
- Presented at the
*IEEE Conf. on Decision and Control* - Phoenix , Arizona , December, 7-10, 1999
- [PDF]

### " On The Synthesis Of Communicating Controllers With Decentralized Information Structures For Discrete-Event Systems "

*The decentralized control problem addressed in this paper is that of several communicating supervisory con trollers, each with different information, working in concert to exactly achieve a given legal sublanguage of the uncontrolled system's language model. A general model is reviewed for dealing with this class of problems. Existence, non-uniqueness, and some synthesis results to the above-mentioned problem are given.*

- by G. Barrett and S. Lafortune
- Presented at the
*IEEE Conf. on Decision and Control* - Tampa , Florida , December, 16-18, 1998
- [PDF]

### " Coordinated Decentralized Protocols For Failure Diagnosis Of Discrete Event Systems "

*We address the problem of failure diagnosis in discrete event systems with decentralized information. We propose a coordinated decentralized architecture consisting of two local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in [1] for centralized systems, to the proposed coordinated decentralized architecture. We specify three protocols that realize the proposed architecture. We analyze the diagnostic properties of these protocol. The key features of the proposed protocols are: (i) they achieve, each under a set of assumptions, the same diagnostic performance as the centralized diagnoser; and (ii) they highlight the performance vs. complexity tradeo that arises in coordinated decentralized architectures.*

- by R. Debouk, S. Lafortune, and D. Teneketzis
- Presented at the
*IEEE Conf. on Decision and Control* - Tampa , Florida , December, 16-18, 1998
- [PDF]

### " A Novel Framework For Decentralized Supervisory Control With Communication "

*The decentralized control problem that we address in this paper is that of several communicating supervisory controllers, each with di erent information, working in concert to exactly achieve a given legal sublanguage of the uncontrolled system's language model. We present a novel information structure formalism for dealing with this class of problems. Preliminary results are presented which elucidate a fundamental concept in decentralized control problems: the importance of controllers anticipating future possible communications.*

- by G. Barrett and S. Lafortune
- Presented at the
*IEEE Conf. on Systems, Man, and Cybernetics* - San Diego , California , October, 11-14, 1998
- [PDF]

### " A Coordinated Decentralized Protocol For Failure Diagnosis Of Discrete Event Systems "

*We address the problem of failure diagnosis in discrete event systems with decentralized information. We propose a coordinated decentralized architecture consisting of two local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in [1] for centralized systems, to the proposed coordinated decentralized architecture. We specify one protocol that realizes the proposed architecture. We analyze the diagnostic properties of this protocol. The key feature of the proposed protocol is that it achieves the same diagnostic performance as the centralized diagnoser.*

- by R. Debouk, S. Lafortune, and D. Teneketzis
- Presented at the
*International Workshop on Discrete Event Systems* - Cagliari , Italy , August, 26-28, 1998
- [PDF]

## Journals

### " Distributed Diagnosis of Place-Bordered Petri Nets "

*This paper studies on-line fault detection and isolation of modular dynamic systems modeled as sets of place-bordered Petri nets. The common places among the set of Petri nets modeling a system capture coupling of various system components. The transitions are labeled by events, some of which are unobservable, i.e., not directly recorded by the sensors attached to the system. The events whose occurrence must be diagnosed have unobservable transition labels. These events model faults or other significant changes in the system state. The existing theory of diagnosis of discrete-event systems is extended in the context of the above model. The modular structure of the system is exploited by a distributed algorithm for fault diagnosis. A Petri net diagnoser is associated to every Petri net and the diagnosers communicate in real-time during the diagnostic process when the token count of common places changes. A merge function is defined to combine the individual diagnoser states and recover the complete diagnoser state that would be obtained under a monolithic approach. Strategies that reduce the communication overhead are presented. The software implementation of the distributed algorithm is discussed.*

- by S. Genc and S. Lafortune
*IEEE Transactions on Automation Science and Engineering*- Vol. 0, No. 0, January, 2007 pp. 0-0
- [PDF]

### " Diagnostic Decentralise Des Systemes A Evenements Discrets "

'*We consider the detection and identification of unobservable events in the behavior of discrete event systems. We study decentralized diagnosis architectures where several sites observe the system behavior, each site having its own set of observable events. These sites do not communicate among each other but they send their local diagnostic decisions to a coordinating site that implements a simple memoryless Boolean fusion rule. Several new results are presented in the context of such architectures, with special focus on the use of conditional decisions by the local sites.*

- by S. Lafortune, Y. Wang, T.-S. Yoo
*Journal Europeen des Systemes Automatises (RS-JESA)*- Vol. 99, No. 99, August, 2005 pp. 95-110
- [PDF]

### " Diagnosis Of Intermittent Faults "

*The diagnosis of “intermittent” faults in dynamic systems modeled as discrete event systems is considered. In many systems, faulty behavior often occurs intermittently, with fault events followed by corresponding “reset” events for these faults, followed by new occurrences of fault events, and so forth. Since these events are usually unobservable, it is necessary to develop diagnostic methodologies for intermittent faults. Prior methodologies for detection and isolation of permanent faults are no longer adequate in the context of intermittent faults, since they do not account explicitly for the dynamic behavior of these faults. This paper addresses this issue by: (i) proposing a modeling methodology for discrete event systems with intermittent faults; (ii) introducing new notions of diagnosability associated with fault and reset events; and (iii) developing necessary and sufficient conditions, in terms of the system model and the set of observable events, for these notions of diagnosability. The definitions of diagnosability are complementary and capture desired objectives regarding the detection and identification of faults, resets, and the current system status (namely, is the fault present or absent). The associated necessary and sufficient conditions are based upon the technique of “diagnosers” introduced in earlier work, albeit the structure of the diagnosers needs to be enhanced to capture the dynamic nature of faults in the system model. The diagnosability conditions are verifiable in polynomial time in the number of states of the diagnosers.*

- by O. Contant, S. Lafortune and D. Teneketzis
*Discrete Event Dynamic Systems: Theory and Applications*- Vol. 14, No. 2, April, 2004 pp. 171-202
- [PDF]

### " Deciding Coobservability Is PSPACE-Complete "

*In this paper we reduce the deterministic finite-state automata intersection problem to the problem of deciding coobservability of regular languages using a polynomial-time many-one mapping. This demonstrates that the problem of deciding coobservability for languages marked by deterministic finite-state automata is PSPACE-complete. We use a similar reduction to reduce the deterministic finite-state automata intersection problem to deciding other versions of coobservability introduced in [Yoo,Lafortune:2002]. These results imply that the coobservability of regular languages most likely cannot be decided in polynomial time unless we make further restrictions on the languages. These results also show that deciding decentralized supervisor existence is PSPACE-complete and therefore probably intractable.*

- by K. Rohloff, T. Yoo and S. Lafortune
*IEEE Trans. on Automatic Control*- Vol. 48, No. 11, November, 2003 pp. 1995-1999
- [PDF]

### " On the Synthesis of Safe Control Policies In Decentralized Control of Discrete-Event Systems "

*State estimation and safe controller synthesis for a general form of decentralized control architecture for discrete event systems is investigated. For this architecture, controllable events are assigned to be either *conjunctive* or *disjunctive*. A new state estimator that accounts for past local control actions when calculating the set of estimated system states is presented. The new state estimator is applied to a previous general decentralized control law. The new control method generates a controlled language at least as large as that generated by the original method if a safety condition is satisfied. An algorithm for generating locally maximal control policies for a given state estimate is also discussed. The algorithm allows an amount of *steering* of the controlled system through an event priority mechanism.*

- by K. Rohloff and S. Lafortune
*IEEE Trans. on Automatic Control*- Vol. 48, No. 6, June, 2003 pp. 1064-1068
- [PDF]

### " Polynomial-time Verification of Diagnosability of Partially-observed Discrete-Event Systems "

*The problem of verifying the properties of diagnosability and I-diagnosability is considered. We present new polynomial-time algorithms for deciding diagnosability and I-diagnosability. These algorithms are based on the construction of a nondeterministic automaton called a verifier.*

- by T. Yoo and S. Lafortune
*IEEE Trans. on Automatic Control*- Vol. 47, No. 9, September, 2002 pp. 1491-1495
- [PDF]

### " NP-Completeness of Sensor Selection Problems Arising In Partially-observed Discrete-Event Systems "

*We consider the three properties of diagnosability, normality, and observability of discrete-event systems. In each case, we consider the problem of finding an observable event set with minimum cardinality such that the property under consideration holds. We prove that these search problems are computationally hard by showing that the corresponding decision problems are NP-complete.*

- by T. Yoo and S. Lafortune
*IEEE Trans. on Automatic Control*- Vol. 47, No. 9, September, 2002 pp. 1495-1499
- [PDF]

### " A General Architecture for Decentralized Supervisory Control of Discrete-Event Systems "

*We consider a generalized form of the conventional decentralized control architecture for discrete-event systems where the control actions of a set of supervisors can be *fused* using both union and intersection of enabled events. Namely, the supervisors agree a priori on choosing *fusion by union* for certain controllable events and *fusion by intersection* for certain other controllable events. We show that under this architecture, a larger class of languages can be achieved than before since a relaxed version of the notion of co-observability appears in the necessary and sufficient conditions for the existence of supervisors. The computational complexity of verifying these new conditions is studied. A method of partitioning the controllable events between *fusion by union* and *fusion by intersection* is presented. The algebraic properties of co-observability in the context of this architecture are presented. We show that appropriate combinations of fusion rules with corresponding decouple local decision rules guarantee the safety of the closed-loop behavior with respect to a given specification that is not co-observable. We characterize an *optimal* combination of fusion rules among those combinations guaranteeing the safety of the closed-loop behavior. In addition, a simple supervisor synthesis technique generating the infimal prefix-closed controllable and co-observable superlanguage is presented.*

- by T. Yoo and S. Lafortune
*Discrete Event Dynamic Systems: Theory and Applications*- Vol. 12, No. 3, July, 2002 pp. 335-377
- [PDF]

### " Coordinated Decentralized Protocols for Failure Diagnosis of Discrete Event Systems "

*We address the problem of failure diagnosis in discrete event systems with decentral ized information. We propose a coordinated decentralized architecture consisting of local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in [19] for centralized systems, to the proposed coordinated decentralized architecture. We specify three protocols that realize the proposed architecture; each protocol is de ned by the diagnostic information generated at the local sites, the communication rules used by the local sites, and the coordinator's decision rule. We analyze the diagnostic properties of each protocol. We also state and prove conditions for a language to be diagnosable under each protocol. These conditions are checkable on-line. The on-line diagnostic process is carried out using the diagnosers introduced in [19] or a slight variation of these diagnosers. The key features of the proposed protocols are: (i) they achieve, each under a set of assumptions, the same diagnostic performance as the centralized diagnoser; and (ii) they highlight the *performance vs. complexity* tradeoff that arises in coordinated de- centralized architectures. The correctness of two of the protocols relies on some stringent global ordering assumptions on message reception at the coordinator's site, the relaxation of which is brie y discussed.*

- by R. Debouk, S. Lafortune, and D. Teneketzis
*Discrete Event Dynamic Systems: Theory and Applications*- Vol. 10, No. 1, January, 2000 pp. 33-86
- [PDF]

### " Bisimulation, the Supervisory Control Problem and Strong Model Matching for Finite State Machines "

*A fundamental relationship between the controllability of a language with respect to another lan- guage and a set of uncontrollable events in the Supervisory Control Theory initiated by Ramadge and Wonham [24] and bisimulation of automata models is derived. The theoretical results relating bisimulation to controllability support an efficient solution to the Basic Supervisory Control Problem. Using Fernandez' [12] generalization of the partition re nement algorithm of Paige and Tarjan [22], it is possible to nd a partition which represents the supremal controllable sublan- guage of an automaton with respect to the language of another automaton and a set of events in a worst-case running time of O(mlog(n)), where m is the number of transitions and n is the number of states. Utilizing the bisimulation property of language controllability and derived relationships between automata languages and input/output nite-state machine behaviors, a precise relation- ship is formally derived between Supervisory Control Theory and the system-theoretic problem posed by DiBenedetto et al. [7] called Strong Input/Output FSM Model Matching. Speci cally, it is proven that in deterministic settings instances of each problem can be mapped to the other framework and solved.*

- by G. Barrett and S. Lafortune
*Discrete Event Dynamic Systems: Theory and Applications*- Vol. 8, No. 4, December, 1998 pp. 377-429
- [PDF]

## Book Chapters

### " Recent Advances On the Control of Partially-Observed Discrete-Event Systems "

*This paper reviews and discusses some recent results on the control of partially-observed discrete-event systems. Several results related to the synthesis of safe solutions in decentralized control architectures are described and illustrated with examples.*

- by S. Lafortune, K. Rohloff and T. Yoo
*Symposium on the Supervisory Control of Discrete Event Systems*- published by Kluwer Academic Publishers
- [PDF]

## Technical Reports

### " Correlation and Classification of Internet Traffic Anomalies "

*A demonstration and sensitivity analysis is presented of a hierarchical framework to classify and assess Internet traffic anomalies. The goal is to monitor, classify, correlate and assess a large number of alerts, which correspond to anomalies, at spatially distributed sites on the Internet. At each node of the hierarchy, multi-criteria decision making (MCDM), specifically the Electre Tri method, is used to assign a risk index to each anomaly. Using historical data from the Abilene Internet2 Backbone Network, experiments are conducted to illustrate the tool's response to a distributed denial of service (DDoS) attack. In addition, experiments were performed to conduct a sensitivity analysis of the approach.*

- by Patrick Macnamara
*Control Group Report ≠CGR 05-10*- Department of EECS, University of Michigan
- [PDF]

### " Diagnosis of Distributed Discrete Event Systems: Architecture and Modular Verification Approach "

*Monitoring and diagnosis methodologies that are based upon discrete-event models of dynamic systems have proved successful in many application areas including document processing systems, heating, ventilation, and air-conditioning systems, intelligent transportation systems, chemical process control, and telecommunication networks. Most of the discrete-event fault diagnosis methodologies that have been studied in the literature require a “monolithic” model of the system under consideration for diagnosability analysis and/or construction of the diagnostic protocol; see (Lafortune et al., 2001) and the references therein. Notable exceptions include the approaches developed in (Holloway and Chand, 1994; Ricker and Fabre, 2000; Fabre et al., 2002; Garc´ia et al., 2002; Su et al., 2002; Debouk et al., 2002; Genc and Lafortune, 2003) where the modular structure of the underlying system is exploited by the respective monitoring or diagnostic protocols. This paper has a similar objective, although the approach adopted is different from those in the above references. We consider systems that are modeled by the parallel composition of a set of automata. Each individual automaton models a component or subsystem of the overall system. The coupling of these system components is captured by the use of common events. We are concerned with systems where the construction of the complete system model (namely, the monolithic model obtained by performing the parallel composition of the set of individual automata) is computationally difficult or intractable, making the use of fault diagnosis methodologies such as the “Diagnoser Approach” in (Sampath et al., 1995; Debouk et al., 2000; Contant et al., 2002) impractical. Therefore, it is necessary to develop modular approaches that are computationally tractable for analyzing the diagnosability properties of the system and for synthesizing appropriate diagnostic protocols. By “modular approaches” we mean approaches that exploit the structure of the system as captured by the individual automata and their respective sets of common events. The first contribution of this paper is to present a new notion of diagnosability that is explicitly geared towards systems with modular representations. This notion of modular diagnosability, presented in Section 3, is adapted from the notion of diagnosability introduced in (Sampath et al., 1995). Necessary and sufficient conditions for modular diagnosability are presented and discussed. The second contribution of this paper is the development in Section 4 of a novel algorithm for verifying modular diagnosability. This algorithm (abbreviated MDA hereafter) proceeds incrementally by including the automata models of other system components only if they are required to draw definitive conclusions about the diagnosability of faults within a given system component. A key assumption made in the development of MDA is that all common events among two or more system components are observable.*

- by O. Contant, S. Lafortune, and D. Teneketzis
*Control Group Report ≠CGR 04-04*- Department of EECS, University of Michigan
- [PDF]

### " Failure Diagnosis of Stochastic Automata "

*Diagnosability of finite-state machines as introduced by Sampath et al. requires certainty that a failure has occurred in order to diagnose it. However, in many situations, it may be practical to diagnose failures based on them having a high likelihood of occurring, even if the failure has not occurred with certainty. This paper extends the diagnosis methodology developed for logical finite state machines to stochastic automata. By incorporating probabilistic information into the model, we are able to define the weaker diagnosability conditions of A-diagnosability and AA-diagnosability. Off-line conditions for A-diagnosability and AA-diagnosability are determined through the construction of a stochastic diagnoser; we also show how the stochastic diagnoser can be used for online diagnosis of failure events.*

- by David Thorsley and Demosthenis Teneketzis
*Control Group Report ≠CGR 03-05*- Department of EECS, University of Michigan
- [PDF]

### " Deciding Coobservability Is PSPACE-Complete "

*In this paper we reduce the deterministic finite-state automata intersection problem to the problem of deciding coobservability of regular languages using a polynomial-time many-one mapping. This demonstrates that the problem of deciding coobservability for languages marked by deterministic finite-state automata is PSPACE-complete. We use a similar reduction to reduce the deterministic finite-state automata intersection problem to deciding other versions of coobservability introduced in [Yoo,Lafortune,2002]. These results imply that coobservability of regular languages most likely cannot be decided in polynomial time unless we make further restrictions on the languages. most likely cannot be decided in polynomial time unless we make further restrictions on the languages. These results also show that deciding decentralized supervisor existence is PSPACE-complete and therefore probably intractable.*

- by K. Rohloff and S. Lafortune
*Control Group Report ≠CGR 03-08*- Department of EECS, University of Michigan
- [PDF]

### " Space Efficient Methods for Testing Reachability With Applications To Supervisory Control of Discrete-Event Systems "

*All known methods of deciding coobservability use exponential space and we demonstrate that we can decide coobservability using polynomial space. Coobservability is one of the necessary and sufficient conditions for deciding decentralized controller existence. Our method for deciding coobservability is based on a deterministic space efficient method we introduce for deciding state reachability for finite state systems. This reachability decision method runs in space O(q^2) where q is the size of the encoding of a system state. This memory bound allows us to decide reachability in large state space systems in a manner that avoids space constraints caused by the state explosion problem. However, there is a space-time tradeoff and our methods are potentially expensive in computation time. We discuss some experimental results that demonstrate this new method of deciding coobservability is more space efficient than the current known method but the time-space tradeoff causes these algorithms to be very inefficient in time.*

- by K. Rohloff and S. Lafortune
*Control Group Report ≠CGR 03-08*- Department of EECS, University of Michigan
- [PDF]

### " Diagnosis of Discrete Event Systems: The Case of Intermittent Fault "

*The diagnosis of “intermittent” faults in dynamic systems modeled as discrete event systems is considered. Earlier work on failure diagnosis of discrete event systems assumed permanent faults (or failures). In many systems, faulty behavior often occurs intermittently, with fault events followed by corresponding “reset” events for these faults, followed by new occurrences of fault events, and so forth. Since these events are usually unobservable, it is necessary to develop diagnostic methodologies for intermittent faults. Prior methodologies for detection and isolation of permanent faults are no longer adequate in the context of intermittent faults, since they do not account explicitly for the dynamic behavior of these faults. This paper addresses this issue by: (i) proposing a modeling methodology for discrete event systems with intermittent faults; (ii) introducing new notions of diagnosability associated with fault and reset events; and (iii) developing necessary and sufficient conditions, in terms of the system model and the set of observable events, for these notions of diagnosability. The definitions of diagnosability are complementary and capture desired objectives regarding the detection and identification of faults, resets, and the current system status (namely, is the fault present or absent). The associated necessary and sufficient conditions are based upon the technique of “diagnosers” introduced in earlier work, albeit the structure of the diagnosers needs to be enhanced to capture the dynamic nature of faults in the system model. The diagnosability conditions are verifiable in polynomial time in the number of states of the diagnosers.*

- by O. Contant, S. Lafortune, and D. Teneketzis
*Control Group Report ≠CGR 02-05*- Department of EECS, University of Michigan
- [PDF]

### " Advances In State Estimation and Controller Synthesis for General Decentralized Control of Discrete Event Systems "

*Several improvements to decentralized control of discrete-event systems are suggested and investigated. A general form of decentralized control architecure is investigated where controllable events are assigned to be either *permissive* or *antipermissive*. The first improvement suggested in this paper is an enhanced state estimator for local general architecture controllers that accounts for past control actions when calculating the set of estimated system states. The new state estimator is applied to the original general decentralized control law to formulate a new control law. The new general decentralized control law, when used to control to a plant, generates a controlled language at least as large as those generated by the original general decentralized control law if a safety condition is satisfied. Two algorithms for generating maximal local control policies are also presented that allow an amount of *steering* of the controlled system. Several properties of these locally maximal control policies are discussed.*

- by K. Rohloff and S. Lafortune
*Control Group Report ≠CGR 01-11*- Department of EECS, University of Michigan
- [PDF]

### " On the Effect of Communication Delays In Failure Diagnosis of Decentralized Discrete Event Systems "

- by R. Debouk, S. Lafortune, and D. Teneketzis
*Control Group Report ≠CGR 00-04*- Department of EECS, University of Michigan
- [PDF]

### " Decentralized Supervisory Control With Communication "

*The decentralized control problem for discrete-event systems addressed in this paper is that of several communicating supervisory controllers, each with di erent information, working in concert to exactly achieve a given legal sublanguage of the uncontrolled system's lan- guage model. A novel information structure model is presented for dealing with this class of problems. Existence results are given for the cases of when controllers do and do not anticipate future communications, and a synthesis procedure is given for the case when controllers do not anticipate communications. Several conditions for optimality of commu- nication policies are presented, and it is shown that the synthesis procedure yields solutions (when they exists for this class of controllers) that are optimal with respect to one of these conditions.*

- by G. Barrett and S. Lafortune
*Control Group Report ≠CGR 98-12*- Department of EECS, University of Michigan
- [PDF]