Dynamic observation in discrete-event system

This dissertation studies problems of dynamic observation in discrete-event systems. In discrete-event systems, agents exist that observe events generated by a system. The agents have some task to fulfill that requires observing the behaviour of the system, such as control of the system or diagnosis of failures in the system. Traditionally in discrete-event systems, agents observe all occurrences of a given event, or no occurrences of that event.;In problems of dynamic observation, certain occurrences of a given event may be observed whereas other occurrences may not be observed. An example scenario of dynamic observation is when an agent uses sensors for observing events which the agent may turn on or off at its leisure. Another example scenario is when the agent receives messages from another agent indicating that certain events in the system have occurred.;This dissertation studies problems related to the above two scenarios, as well as more general scenarios where dynamic observation occurs. First, we study the problem of computing a finite-state representation of how an agent uses its sensors for making event observations. We show that such a representation may be computed in polynomial-time when certain restrictions on how an agent may use its event sensors are imposed. We show that a simple generalization of these restrictions results in the problem of computing the representation being PSPACE-complete.;Second, we study the problem of computing indistinguishable state pairs of finite-state automata. Indistinguishable state pairs are used in the verification of properties involved in solutions to problems of dynamic observation. We demonstrate how indistinguishable state pairs may be computed and how they may be used to verify such properties.;Third, we study cases in dynamic observation where observing more event occurrences permits agents to more precisely estimate the state of the system. We apply these results in the solution to a problem where two agents must accomplish their tasks while communicating as little as possible to one another.