hscc09

Grosu

Finite Automata as Time-Invariant Linear Systems: Observability, Reachability and More.*

R. Grosu.

We show that regarding finite automata (FA) as discrete, time-invariant linear systems over semimodules, allows to: (1) Express FA minimization and FA determinization as particular observability and reachability transformations of FA, respectively; (2) Express FA pumping as a property of the FA's reachability matrix; (3) Derive canonical forms for FAs. These results are to our knowledge new, and they may support a fresh look into hybrid automata properties, such as minimality. Moreover, they may allow to derive generalized notions of characteristic polynomials and associated eigenvalues, in the context of FA.

In Proc. of HSCC'09, the 12th International Conference on Hybrid Systems: Computation and Control, San Francisco, USA, April, 2009, pp. 194-208, Springer, LNCS 5469.

*This work was supported by the NSF Faculty Early Career Development Award CCR01-33583 and the NSF CCF05-23863 Award.