RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






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


Mat. Zametki, 2011, Volume 90, Issue 3, Pages 422–430 (Mi mz6191)  

This article is cited in 1 scientific paper (total in 1 paper)

Slowly Synchronizing Automata with Zero and Uncovering Sets

E. V. Pribavkina

Ural State University, Ekaterinburg

Abstract: Using the combinatorial properties of uncovering sets in a free monoid, we construct a series of finite deterministic synchronizing automata with zero for which the shortest synchronizing word has length $n^2/4+n/2-1$, where $n$ is the number of states.

Keywords: free monoid, uncovering set, deterministic and nondeterministic automaton, synchronizing automaton (with zero), synchronizing word, maximal code

DOI: https://doi.org/10.4213/mzm6191

Full text: PDF file (512 kB)
References: PDF file   HTML file

English version:
Mathematical Notes, 2011, 90:3, 411–417

Bibliographic databases:

UDC: 519.713.2
Received: 28.08.2008
Revised: 21.12.2010

Citation: E. V. Pribavkina, “Slowly Synchronizing Automata with Zero and Uncovering Sets”, Mat. Zametki, 90:3 (2011), 422–430; Math. Notes, 90:3 (2011), 411–417

Citation in format AMSBIB
\Bibitem{Pri11}
\by E.~V.~Pribavkina
\paper Slowly Synchronizing Automata with Zero and Uncovering Sets
\jour Mat. Zametki
\yr 2011
\vol 90
\issue 3
\pages 422--430
\mathnet{http://mi.mathnet.ru/mz6191}
\crossref{https://doi.org/10.4213/mzm6191}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2868370}
\transl
\jour Math. Notes
\yr 2011
\vol 90
\issue 3
\pages 411--417
\crossref{https://doi.org/10.1134/S0001434611090094}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000296476500009}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80155149509}


Linking options:
  • http://mi.mathnet.ru/eng/mz6191
  • https://doi.org/10.4213/mzm6191
  • http://mi.mathnet.ru/eng/mz/v90/i3/p422

    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

    This publication is cited in the following articles:
    1. Singh Sh.N., Krishna K.V., “On Syntactic Complexity of Circular Semi-Flower Automata”, Implementation and Application of Automata, Ciaa 2018, Lecture Notes in Computer Science, 10977, ed. Campeanu C., Springer International Publishing Ag, 2018, 312–323  crossref  isi
  • Математические заметки Mathematical Notes
    Number of views:
    This page:273
    Full text:67
    References:41
    First page:20

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019