CLASSICAL AND LOGIC-BASED DYNAMIC OBSERVERS FOR FINITE AUTOMATA

This paper formulates the state estimation problem for a partially observed input-state-output (N-state) automaton in terms of a classical observer automaton each of whose nodes correspond to the set of states consistent with a particular sequence of observations. It next provides several complexity results about these observers, i.e. bounds their convergence time and sizes, by use of the associated directed acyclic observer. The final part introduces the notion of a logic-based dynamic observer, shows how to encode these observers in predicate calculus, demonstrates an equivalence between classical and logic-based systems and observers, and illustrates some of the advantages of the logic-based approach.