Modeling and analyzing finite state automata in the finite field F2

被引：4

作者：

Reger, J ^{[1
]}

Schmidt, K ^{[1
]}

机构：

[1] Univ Erlangen Nurnberg, Dept Elect & Elect Commun Engn, Inst Automat Control, D-91058 Erlangen, Germany

来源：

MATHEMATICS AND COMPUTERS IN SIMULATION | 2004年 / 66卷 / 2-3期

关键词：

finite state automata; linear modular systems; finite fields; feedback shift registers;

D O I：

10.1016/j.matcom.2003.11.005

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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 behavior of these automata are recalled. With respect to these linear models, the cyclic structure of the state space is shown to be determined only by the periods of the elementary divisor polynomials of the system dynamics. An example illustrates the analysis procedure. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.

引用

页码：193 / 206

页数：14