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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
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

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


Linking options:
  • http://mi.mathnet.ru/eng/ppi1123
  • http://mi.mathnet.ru/eng/ppi/v20/i1/p74

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:122
    Full text:50

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021