A finite field framework for modeling, analysis and control of finite state automata

Date

2004-09-01

Author

Reger, Johann
Schmidt, Klaus Verner

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

228
views

0
downloads

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 F-2 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 F2. Examples illustrate the main steps of our method.

Subject Keywords

Control and Systems Engineering, Modelling and Simulation, Software, Applied Mathematics, Computer Science Applications

URI

https://hdl.handle.net/11511/41882

Journal

Mathematical and Computer Modelling of Dynamical Systems

DOI

https://doi.org/10.1080/13873950412331300142

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

A state prediction scheme for discrete time nonlinear dynamic systems Demirbaş, Kerim (Informa UK Limited, 2007-01-01) A state prediction scheme is proposed for discrete time nonlinear dynamic systems with non-Gaussian disturbance and observation noises. This scheme is based upon quantization, multiple hypothesis testing, and dynamic programming. Dynamic models of the proposed scheme are as general as dynamic models of particle predictors, whereas the nonlinear models of the extended Kalman (EK) predictor are linear with respect to the disturbance and observation noises. The performance of the proposed scheme is compared wi...
An improved method for inference of piecewise linear systems by detecting jumps using derivative estimation Selcuk, A. M.; Öktem, Hüseyin Avni (Elsevier BV, 2009-08-01) Inference of dynamical systems using piecewise linear models is a promising active research area. Most of the investigations in this field have been stimulated by the research in functional genomics. In this article we study the inference problem in piecewise linear systems. We propose first identifying the state transitions by detecting the jumps of the derivative estimates, then finding the guard conditions of the state transitions (thresholds) from the values of the state variables at the state transitio...
Verification of Modular Diagnosability With Local Specifications for Discrete-Event Systems Schmidt, Klaus Verner (Institute of Electrical and Electronics Engineers (IEEE), 2013-09-01) In this paper, we study the diagnosability verification for modular discrete-event systems (DESs), i.e., DESs that are composed of multiple components. We focus on a particular modular architecture, where each fault in the system must be uniquely identified by the modular component where it occurs and solely based on event observations of that component. Hence, all diagnostic computations for faults to be detected in this architecture can be performed locally on the respective modular component, and the obt...
Modeling and analyzing finite state automata in the finite field F 2 Reger, J.; Schmidt, Klaus Verner (Elsevier BV, 2004-06-29) A method for determining multilinear state space models for general finite state automata is presented. The obtained model resides on F-2, the finite field of characteristic 2 with the operations addition and multiplication, both carried out modulo 2. It is functionally complete in the sense that it is capable of describing all finite state automata, including non-deterministic and partially defined automata. For those cases in which the model over F-2 is linear, means for a complete analysis of the cyclic ...
A new likelihood approach to autonomous multiple model estimation Söken, Halil Ersin (Elsevier BV, 2020-04-01) This paper presents an autonomous multiple model (AMM) estimation algorithm for hybrid systems with sudden changes in their parameters. Estimates of Kalman filters (KFs) that are tuned and employed for different system modes are merged based on a newly defined likelihood function without any necessity for filter interaction. The proposed likelihood function is composed of two measures, the filter agility measure and the steady-state error measure. These measures are derived based on filter adaptation rules....

Citation Formats

J. Reger and K. V. Schmidt, “A finite field framework for modeling, analysis and control of finite state automata,” Mathematical and Computer Modelling of Dynamical Systems, pp. 253–285, 2004, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41882.