Modeling and analyzing finite state automata in the finite field F2

J. Reger and K. Schmidt

Mathematics and Computers in Simulation (MATCOM), 2004, vol. 66, issue 2, 193-206

Abstract: A method for determining multilinear state space models for general finite state automata is presented. The obtained model resides on F2, 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 F2 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.

Keywords: Finite state automata; Linear modular systems; Finite fields; Feedback shift registers (search for similar items in EconPapers)
Date: 2004
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475403002040
Full text for ScienceDirect subscribers only

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:eee:matcom:v:66:y:2004:i:2:p:193-206

DOI: 10.1016/j.matcom.2003.11.005

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().