RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



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






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


Diskr. Mat., 2008, Volume 20, Issue 2, Pages 100–121 (Mi dm1006)  

This article is cited in 2 scientific papers (total in 2 papers)

Minimality and deadlockness of multitape automata

R. I. Podlovchenko, V. E. Khachatryan


Abstract: We consider the class $M$ of deterministic binary two-tape automata for which those states of the automaton where reading from the additional second tape is implemented permit to continue the calculation only in the case where the read symbol is fixed in advance for all automata. For the automata of the class $M$, the so-called generalised minimisation problem is considered. This problem consists in finding all automata which are minimal in the number of states in any class of equivalent automata of $M$. In the paper, the decidability of the generalised minimisation problem in $M$ is proved and a procedure to solve this problem is described and analysed.

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

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

English version:
Discrete Mathematics and Applications, 2008, 18:3, 271–292

Bibliographic databases:

UDC: 519.7
Received: 25.12.2007

Citation: R. I. Podlovchenko, V. E. Khachatryan, “Minimality and deadlockness of multitape automata”, Diskr. Mat., 20:2 (2008), 100–121; Discrete Math. Appl., 18:3 (2008), 271–292

Citation in format AMSBIB
\Bibitem{PodKha08}
\by R.~I.~Podlovchenko, V.~E.~Khachatryan
\paper Minimality and deadlockness of multitape automata
\jour Diskr. Mat.
\yr 2008
\vol 20
\issue 2
\pages 100--121
\mathnet{http://mi.mathnet.ru/dm1006}
\crossref{https://doi.org/10.4213/dm1006}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2450036}
\zmath{https://zbmath.org/?q=an:1191.68401}
\elib{http://elibrary.ru/item.asp?id=20730246}
\transl
\jour Discrete Math. Appl.
\yr 2008
\vol 18
\issue 3
\pages 271--292
\crossref{https://doi.org/10.1515/DMA.2008.021}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-47249097167}


Linking options:
  • http://mi.mathnet.ru/eng/dm1006
  • https://doi.org/10.4213/dm1006
  • http://mi.mathnet.ru/eng/dm/v20/i2/p100

    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. Podlovchenko R.I., Khachatryan V.E., “Razreshimost problemy ekvivalentnykh preobrazovanii v odnom mnozhestve dvukhlentochnykh avtomatov i postroenie vsekh minimalnykh avtomatov v etom mnozhestve”, Informatsionnye sistemy i tekhnologii, 2009, no. 4, 12–17  elib
    2. R. I. Podlovchenko, V. E. Khachatryan, “A complete solution of the minimisation problem for a set of binary two-tape automata”, Discrete Math. Appl., 20:4 (2010), 451–466  mathnet  crossref  crossref  mathscinet  elib
  • Дискретная математика
    Number of views:
    This page:382
    Full text:120
    References:49
    First page:11

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