FG DES libFAUDES DESTool	LRT >> EEI >>
About Research Publications Download Links

Algebraic Methods for Modeling, Analysis and Synthesis of Discrete Event Systems

In this project we establish a link between the classical system theoretical framework of a continuous time state space and the world of discrete event systems. This link is given by the algebraic concept of a field. In the continuous world, typically, this field is the field of real or complex numbers. Restricting our perspective on discrete event systems with a finite number of system variables (e.g. finite state automata), so-called finite fields play an analogous, important rôle. Apart from the plenty of analogies which can be drawn from classical continuous system theory, additional propositions can be derived due to the finiteness of the field. As a result, algebraic systems over finite fields contain additional structure, of which, advantage can be taken most easily in the linear case.

In linear circuit theory, the use of finite fields is common practice since the early sixties. But nevertheless, most contributions left the input channels unused. In our contributions, we interpret systems from circuit theory as subclasses of finite state automata and link the inputs with the states by an adequate feedback structure in order to impose specifications on the controlled automaton. To this end, we adapt methods from continuous control theory on the finite field scenario.

Current research on systems over finite fields concentrates on the following aspects:

• Modeling of Finite State Automata
  
  Starting from the scratch or based on a given automaton model a state space model over a finite field can be derived. In such a model, an automaton state is represented by a state vector in a finite state space, similarly, events that impose conditions on the state transition are represented by input vectors in a finite input space. It can be shown that all transition relations, governing admissible state transitions with respect to a given input vector, can be written in a so-called Reed-Muller-Form. The Reed-Muller form is a canonical polynomial representation, which exists for arbitrary functions over a finite field. Among others, one issue of research is the development of efficient algorithms for obtaining the Reed-Muller form of the transition relations for non-deterministic automata.

• System Analysis
  
  Once a finite field model is available, it can be used for analyzing the properties of the modeled discrete event system. Here, one major analysis task is to determine the state space decomposition into invariant subspaces (induced by the transition relation), which typically consists of cyclic states and/or of tree states. In the case of linear systems, necessary and sufficient conditions have been deduced that allow the determination of the entire state space structure. In the nonlinear case, Gröbner-basis or principal ideal representations for the respective nonlinear transition relations are appropriate means for an efficient analysis - still work in progress.

• Synthesis using Feedback
  
  Provided that a system model over a finite field is controllable in some sense, closing the loop by using state feedback is a (continuous world) standard method for synthesizing desired system properties of the overall closed-loop system. If the system model is linear then an image domain representation of the transition relation, an adaption of the z-transform and of the polynomial approach, turns out to be tailored for fixing closed-loop properties by specifying closed-loop system invariants. Concerning nonlinear system models, a variety of research activities is given by employing polynomial state feedback for setting the closed-loop behavior.

This project was conducted by Hans Reger with support by the German National Research Foundation (Deutsche Forschungsgemeinschaft, DFG).