Problemy Peredachi Informatsii
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

 Probl. Peredachi Inf., 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.

Full text: PDF file (827 kB)

English version:
Problems of Information Transmission, 1984, 20:1, 56–63

Bibliographic databases:

UDC: 621.391.1:62-507

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

Citation in format AMSBIB
\Bibitem{Boi84}
\by A.~N.~Boiko
\paper On the Lower Bound for the Number of States of Deterministic Intelligent Automata
\jour Probl. Peredachi Inf.
\yr 1984
\vol 20
\issue 1
\pages 74--81
\mathnet{http://mi.mathnet.ru/ppi1123}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=776768}
\zmath{https://zbmath.org/?q=an:0544.68043}
\transl
\jour Problems Inform. Transmission
\yr 1984
\vol 20
\issue 1
\pages 56--63