Open AccessRepresenting stand-alone automata by characteristic polynomials over a finite field
Author(s) -
В. М. Захаров,
S.V. Shalagin,
Б. Ф. Эминов
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1658/1/012077
Subject(s) - mathematics , deterministic automaton , minimal polynomial (linear algebra) , automaton , characteristic polynomial , sequence (biology) , ergodic theory , polynomial , discrete mathematics , finite state machine , set (abstract data type) , field (mathematics) , stochastic matrix , two way deterministic finite automaton , büchi automaton , matrix (chemical analysis) , polynomial matrix , quantum finite automata , algorithm , matrix polynomial , pure mathematics , automata theory , computer science , markov chain , theoretical computer science , mathematical analysis , materials science , composite material , biology , genetics , programming language , statistics
This paper proposes a method of representing a deterministic stand-alone output automaton by a minimal characteristic polynomial over a finite field. It is shown that defining various automaton transition and output functions allows using the algorithm developed to build the sets of minimal polynomials, different in their powers. Estimates of the relevant sets are given here. We have identified the relation between a characteristic minimal polynomial and an ergodic stochastic matrix defining the sequence developed by a stand-alone automaton. It is shown that the minimal degree of a characteristic polynomial depends linearly on the power of the automaton state set and on the accuracy of representing the elements of a given limiting vector of a stochastic matrix.