RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

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

This article is cited in 3 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.

UDC: 519.7

Received: 25.12.2007

DOI: 10.4213/dm1006


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

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024