Geodesic
Minimality and deadlockness of multitape automata
Diskretnaya Matematika, Tome 20 (2008) no. 2, pp. 100-121.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2008_20_2_a7,
     author = {R. I. Podlovchenko and V. E. Khachatryan},
     title = {Minimality and deadlockness of multitape automata},
     journal = {Diskretnaya Matematika},
     pages = {100--121},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_2_a7/}
}
TY  - JOUR
AU  - R. I. Podlovchenko
AU  - V. E. Khachatryan
TI  - Minimality and deadlockness of multitape automata
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 100
EP  - 121
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_2_a7/
LA  - ru
ID  - DM_2008_20_2_a7
ER  - 
%0 Journal Article
%A R. I. Podlovchenko
%A V. E. Khachatryan
%T Minimality and deadlockness of multitape automata
%J Diskretnaya Matematika
%D 2008
%P 100-121
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2008_20_2_a7/
%G ru
%F DM_2008_20_2_a7
R. I. Podlovchenko; V. E. Khachatryan. Minimality and deadlockness of multitape automata. Diskretnaya Matematika, Tome 20 (2008) no. 2, pp. 100-121. http://geodesic.mathdoc.fr/item/DM_2008_20_2_a7/

[1] Rabin M. O., Skott D., “Konechnye avtomaty i problemy ikh razresheniya”, Kibern. sb., 4 (1962), 58–91

[2] Grifliths T. V., “The unsolvability of the equivalence problem for $\lambda$-free nondeterministic generalized machines”, J. ACM, 15 (1968), 409–413 | DOI | MR

[3] Bird M., “The equivalence problem for deterministic two-tape automata”, J. Comp. Syst. Sci., 7:4 (1973), 218–236 | MR | Zbl

[4] Harju T., Karhumaki J., “The equivalence problem of multitape finite automata”, Theoret. Comp. Sci., 78:2 (1991), 347–355 | DOI | MR | Zbl

[5] Lakkhem D. K., Park D. M., “O formalizovannykh kompyuternykh programmakh”, Kibern. sb., 12 (1975), 78–114

[6] Tamm H., On minimality and size reduction of one-tape and multitape finite automata, Univ. Helsinki, Helsinki, 2004 | Zbl

[7] Khachatryan V. E., “Reshenie obobschennoi problemy minimizatsii dlya dvukhlentochnykh avtomatov s odnoi fiksirovannoi lentoi”, Dokl. RAN, 411:3 (2006), 314–318 | MR

[8] Podlovchenko R. I., “K voprosu ob ekvivalentnykh preobrazovaniyakh algoritmov i programm”, Matem. voprosy kibern., 9 (2000), 25–36 | MR