A Finite Field Framework for Modeling, Analysis and Control of Finite State Automata

Johann Reger and Klaus Schmidt

Mathematical and Computer Modelling of Dynamical Systems, 2004, vol. 10, issue 3-4, 253-285

Abstract: In this paper, we address the modeling, analysis and control of finite state automata, which represent a standard class of discrete event systems. As opposed to graph theoretical methods, we consider an algebraic framework that resides on the finite field >formula form="inline">${\Op F}_2$>/formula> which is defined on a set of two elements with the operations addition and multiplication, both carried out modulo 2. The key characteristic of the model is its functional completeness in the sense that it is capable of describing most of the finite state automata in use, including non-deterministic and partially defined automata. Starting from a graphical representation of an automaton and applying techniques from Boolean algebra, we derive the transition relation of our finite field model. For cases in which the transition relation is linear, we develop means for treating the main issues in the analysis of the cyclic behavior of automata. This involves the computation of the elementary divisor polynomials of the system dynamics, and the periods of these polynomials, which are shown to completely determine the cyclic structure of the state space of the underlying linear system. Dealing with non-autonomous linear systems with inputs, we use the notion of feedback in order to specify a desired cyclic behavior of the automaton in the closed loop. The computation of an appropriate state feedback is achieved by introducing an image domain and adopting the well-established polynomial matrix method to linear discrete systems over the finite field >formula form="inline">${\Op F}_2$>/formula>. Examples illustrate the main steps of our method.

Date: 2004
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/13873950412331300142 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:nmcmxx:v:10:y:2004:i:3-4:p:253-285

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/NMCM20

DOI: 10.1080/13873950412331300142

Access Statistics for this article

Mathematical and Computer Modelling of Dynamical Systems is currently edited by I. Troch

More articles in Mathematical and Computer Modelling of Dynamical Systems from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().