Geodesic
Independent systems of automata in labyrinths
Diskretnaya Matematika, Tome 15 (2003) no. 2, pp. 3-39.

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

We analyse the state of the art of a rather new field of automata theory—the study of behaviour of automata in labyrinths; more than a hundred publications devoted to this topic have been published. We consider key notions, problems, achievements, methods of problem solutions, and open problems in an important direction of this study, the behaviour of independent systems of automata in labyrinths. In a series of cases, we give base assertions in a more strong form and give a more general presentation than the authors of the corresponding papers do. New results are also contained in this survey. 
@article{DM_2003_15_2_a0,
     author = {G. Kilibarda and V. B. Kudryavtsev and \v{S}. M. U\v{s}\'cumli\'c},
     title = {Independent systems of automata in labyrinths},
     journal = {Diskretnaya Matematika},
     pages = {3--39},
     publisher = {mathdoc},
     volume = {15},
     number = {2},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_2_a0/}
}
TY  - JOUR
AU  - G. Kilibarda
AU  - V. B. Kudryavtsev
AU  - Š. M. Ušćumlić
TI  - Independent systems of automata in labyrinths
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 3
EP  - 39
VL  - 15
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_2_a0/
LA  - ru
ID  - DM_2003_15_2_a0
ER  - 
%0 Journal Article
%A G. Kilibarda
%A V. B. Kudryavtsev
%A Š. M. Ušćumlić
%T Independent systems of automata in labyrinths
%J Diskretnaya Matematika
%D 2003
%P 3-39
%V 15
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2003_15_2_a0/
%G ru
%F DM_2003_15_2_a0
G. Kilibarda; V. B. Kudryavtsev; Š. M. Ušćumlić. Independent systems of automata in labyrinths. Diskretnaya Matematika, Tome 15 (2003) no. 2, pp. 3-39. http://geodesic.mathdoc.fr/item/DM_2003_15_2_a0/

[1] Antelmann H., Budach L., Rollik H. A., “On universal traps”, Elektron. Inform.-verarb. Kybernetik, 15 (1979), 123–131 | MR | Zbl

[2] Antelmann H., “An application of the prime number theorem in automata theory”, ICS PAS Rep., 411 (1980), 9–11

[3] Asser G., “Bemerkungen zum labyrinth-problem”, Elektron. Inform.-verarb. Kybernetik, 13 (1977), 203–216 | MR | Zbl

[4] Blum M., Sakoda W., “On the capability of finite automata in 2 and 3 dimensional space”, Proc. 18th Annual Symp. Found. Computer Sci., 1977, 147–161 | MR

[5] Blum M., Kozen D., “On the power of the compass”, Proc. 19th Annual Symp. Found. Computer Sci., 1978, 132–142 | MR

[6] Budach L., “On the solution of the labyrinth problem for finite automata”, Elektron. Inform.-verarb. Kybernetik, 11 (1975), 661–672 | MR | Zbl

[7] Budach L., “Environments, labyrinths and automata”, Lect. Notes Comp. Sci., 56, 1977, 54–64 | MR | Zbl

[8] Budach L., “Automata and labyrinths”, Math. Nachrichten, 86 (1978), 195–282 | DOI | MR | Zbl

[9] Budach L., Meinel Ch., Seminarber, Sekt. Math., Umwelten und Automaten in Umwelten, 23, Humboldt-Univ., Berlin, 1980 | MR | Zbl

[10] Budach L., Meinel Ch., “Environments and automata”, Elektron. Inform.-verarb. Kybernetik, 18 (1982), 3–40 | MR | Zbl

[11] Budach L., Waack S., “On the halting problem for automata in cones”, Elektron. Inform.-verarb. Kybernetik, 18 (1982), 489–499 | MR | Zbl

[12] Bull M., Hemmerling A., “Finite embedded trees and simply connected mazes cannot be searched by halting finite automata”, J. Inf. Process. Cybern., 26 (1990), 65–73 | MR | Zbl

[13] Danecki R., Karpinski M., “Decidability results on plane automata searching mazes”, Proc. 2nd Int. FCT'79 Berlin Conf., 1979, 84–91 | MR | Zbl

[14] Döpp K., “Automaten in Labyrinthen. I”, Elektron. Inform.-verarb. Kybernetik, 7 (1971), 79–94 | MR | Zbl

[15] Döpp K., “Automaten in Labyrinthen. II”, Elektron. Inform.-verarb. Kybernetik, 7 (1971), 167–190 | MR

[16] Fischer P. C., “Multi-tape and infinite-state automata: A survey”, Comm. ACM, 8 (1965), 799–805 | DOI | Zbl

[17] Hemmerling A., “Normed two-plane traps for finite systems of cooperating compass automata”, J. Inf. Process. Cybern., 28 (1987), 453–470 | MR

[18] Hoffmann F., “One pebble does not suffice to search plane labyrinths”, Lect. Notes Computer Sci., 117, 1981, 433–444 | MR | Zbl

[19] Hoffman F., “1-Kiesel-Automaten in Labyrinthen”, Report R-Math-06/82 (AdW der DDR), Berlin, 1982 | MR

[20] Hoffman F., Kriegel K., Quasiplane labyrinths, Preprint P-Math-20/83, AdW der DDR, Berlin, 1983

[21] Kilibarda G., “On the minimum universal collectives of automata for plane labyrinths”, Discrete Math. Appl., 3 (1993), 555–586 | MR | Zbl

[22] Kudryavtsev V. B., Ushchumlich Sh., Kilibarda G., “The behaviour of automata in labyrinths”, Discrete Math. Appl., 3 (1993), 1–28 | MR

[23] Meinel C., “The importance of plane labyrinths”, Elektron. Inform.-verarb. Kybernetik, 18 (1982), 419–422 | MR | Zbl

[24] Müller H., “Endliche Automaten und Labyrinthe”, Elektron. Inform.-verarb. Kybernetik, 7 (1971), 261–264 | MR | Zbl

[25] Müller H., “Automata catching labyrinths with at most three components”, Elektron. Inform.-verarb. Kybernetik, 15 (1979), 3–9 | MR | Zbl

[26] Mylopoulos J., “On the recognition of topological invariants by 4-way finite automata”, Computer Graphics and Image Processing, 1 (1972), 308–316 | DOI | MR

[27] Shannon C. E., “Presentation of a maze-solving machine”, Cybern. Trans. 8th Conf. Josiah Macy Jr. Found., 1951, 173–180

[28] Stahl S., “The embeddings of a graph: A survey”, J. Graph Theory, 2 (1978), 275–298 | DOI | MR | Zbl

[29] Pultr A., Úlehla J., “On two problems of mice”, Rend. Circ. Mat. di Palermo, 31 (1982), 249–262 | MR

[30] Vijayan G., Wigderson A., “Rectilinear graphs and their embeddings”, SIAM J. Comput., 14 (1985), 355–372 | DOI | MR | Zbl

[31] Bogomolov C. A., Zolotykh A. A., Zyrichev A. N., Avtomaty i grafy, Izd-vo Saratovskogo univ., Saratov, 1992

[32] Golovanov A. V., “Ob obkhode labirintov avtomatami, ostavlyayuschimi sled v vershinakh labirinta”, Intellektualnye sistemy, 3 (1998), 193–212

[33] Golubev D. V., “Ob obkhode grafov avtomatami s odnoi nestiraemoi kraskoi”, Intellektualnye sistemy, 4 (1999), 243–272

[34] Zolotykh A. A., “Obkhod labirintov s ogranichennymi v fiksirovannykh napravleniyakh dyrami”, Diskretnaya matematika, 5:1 (1993), 59–69 | MR | Zbl

[35] Zyrichev A. N., “O sinteze avtomata, obkhodyaschego ploskie labirinty s ogranichennymi dyrami”, Diskretnaya matematika, 3:1 (1991), 105–113 | MR | Zbl

[36] Zykov A. A., Osnovy teorii grafov, Nauka, Moskva, 1987 | MR | Zbl

[37] Kilibarda G., “Ob universalnykh labirintakh-lovushkakh dlya konechnykh mnozhestv avtomatov”, Diskretnaya matematika, 2:1 (1990), 72–79 | MR | Zbl

[38] Kilibarda G., “Novoe dokazatelstvo teoremy Budakha–Podkolzina”, Diskretnaya matematika, 3:3 (1991), 135–146 | MR | Zbl

[39] Kilibarda G., Diskretnaya matematika, 5:3 (1993), 116–124 | MR | Zbl

[40] Kilibarda G., “O minimalnykh universalnykh kollektivakh avtomatov dlya ploskikh labirintov”, Diskretnaya matematika, 6:4 (1994), 133–153 | MR | Zbl

[41] Kilibarda G., Ushchumlich Sh., “O labirintakh-lovushkakh dlya kollektivov avtomatov”, Diskretnaya matematika, 5:2 (1993), 29–50 | MR | Zbl

[42] Kilibarda G., Ushchumlich Sh., “O zadache sinteza dlya avtomatov v odnom klasse labirintov”, FILO–MAT, 1995, 743–751 | MR | Zbl

[43] Kilibarda G., “Ob odnorodnykh universalnykh labirintakh-lovushkakh dlya avtomatov” (to appear)

[44] Klimov I. V., “Povedenie v labirintakh nekotorykh avtomatov s kraskoi”, Intellektualnye sistemy, 3:3–4 (1998), 251–268

[45] Kudryavtsev V. B., Podkolzin A. S., Ushchumlich Sh., Vvedenie v teoriyu abstraktnykh avtomatov, Izd-vo MGU, Moskva, 1985

[46] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, Moskva, 1985 | MR

[47] Kudryavtsev V. B., Ushchumlich Sh., Kilibarda G., “O povedenii avtomatov v labirintakh”, Diskretnaya matematika, 5:3 (1992), 3–28

[48] Kurepa I.-A., Modelirovanie povedeniya avtomata v odnom klasse labirintov, Magistr. dissertatsiya, Matem. fakultet, Belgrad, 2000

[49] Maksimovich Z., Magistr. dissertatsiya, Matem. fakultet, Belgrad, 2001

[50] Nasyrov A. Z., “Ob obkhode labirintov avtomatami, ostavlyayuschimi nestiraemye otmetki”, Diskretnaya matematika, 9:1 (1997), 123–133 | MR | Zbl

[51] Nasyrov A. Z., “Ob obkhode avtomatami labirintov v $n$-mernom prostranstve”, Diskretnaya matematika, 12:4 (2000), 121–137 | MR | Zbl

[52] Nasyrov A. Z., “O beskonechnoi lovushke dlya avtomatov so sledom”, Intellektualnye sistemy, 5:1–2 (2000) | MR

[53] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR