|
Problemy Peredachi Informatsii, 1984, Volume 20, Issue 1, Pages 74–81
(Mi ppi1123)
|
|
|
|
Automata Theory
On the Lower Bound for the Number of States of Deterministic Intelligent Automata
A. N. Boiko
Abstract:
The article examines the problem of estimating the complexity of deterministic Moore automata that are intelligent in homogeneous Markov media (HMM). The measure of complexity of the automaton is determined as the number of its internal states. A lower bound $N\geq 2k$ is established for the number of states of automata that are intelligent in HMM; this bound improves the earlier bound $N>k$ (here $k$ is the number of controls). A lower bound $N>k^{3/2}$ is established for the number of states of automata that are intelligent in HMM, for the case in which any of their states is taken as the initial one.
Received: 14.04.1982
Citation:
A. N. Boiko, “On the Lower Bound for the Number of States of Deterministic Intelligent Automata”, Probl. Peredachi Inf., 20:1 (1984), 74–81; Problems Inform. Transmission, 20:1 (1984), 56–63
Linking options:
https://www.mathnet.ru/eng/ppi1123 https://www.mathnet.ru/eng/ppi/v20/i1/p74
|
Statistics & downloads: |
Abstract page: | 158 | Full-text PDF : | 54 |
|