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

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

The behaviour of automata in labyrinths is a rather new field of automata theory, but more than one hundred papers devoted to this topic have been published. In this paper, we consider the key notions, problems, achievements, methods to solve problems, and open problems related to an important direction of this field, the behaviour of collectives 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_3_a0,
     author = {G. Kilibarda and V. B. Kudryavtsev and \v{S}. M. U\v{s}\'cumli\'c},
     title = {Collectives of automata in labyrinths},
     journal = {Diskretnaya Matematika},
     pages = {3--39},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_3_a0/}
}
TY  - JOUR
AU  - G. Kilibarda
AU  - V. B. Kudryavtsev
AU  - Š. M. Ušćumlić
TI  - Collectives of automata in labyrinths
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 3
EP  - 39
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_3_a0/
LA  - ru
ID  - DM_2003_15_3_a0
ER  - 
%0 Journal Article
%A G. Kilibarda
%A V. B. Kudryavtsev
%A Š. M. Ušćumlić
%T Collectives of automata in labyrinths
%J Diskretnaya Matematika
%D 2003
%P 3-39
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2003_15_3_a0/
%G ru
%F DM_2003_15_3_a0
G. Kilibarda; V. B. Kudryavtsev; Š. M. Ušćumlić. Collectives of automata in labyrinths. Diskretnaya Matematika, Tome 15 (2003) no. 3, pp. 3-39. http://geodesic.mathdoc.fr/item/DM_2003_15_3_a0/

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

[2] Blum M., Hewitt C., “Automata on a 2-dimensional tape”, FOCS, 1967, 155–160

[3] Blum M., Sakoda W., “On the capability of finite automata in 2 and 3 dimensional space”, FOCS, 1977, 147–161 | MR

[4] Blum M., Kozen D., “On the power of the compass”, FOCS, 1978, 132–142 | MR

[5] Budach L., “Two pebbles don't suffice”, Lect. Notes Comput. Sci., 118, 1981, 578–589 | MR | Zbl

[6] 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

[7] Coy W., “Of mice and maze”, Elektron. Inform.-verarb. Kybernetik, 14 (1978), 227–232 | MR | Zbl

[8] Ejsmont M., “Problems in labyrinths decidable by pebble automata”, Elektron. Inform.-verarb. Kybernetik, 20 (1984), 623–632 | MR | Zbl

[9] Graw B., “On tape complexity classes and Savitch mazes”, Elektron. Inform.-verarb. Kybernetik, 17 (1981), 501–510 | MR | Zbl

[10] Habasinski Z., Karpinski M., A Codification of Blum–Sakoda 7 Pebbles Algorithm, Pr. Inst. Podstaw Inf. Pol. Akad. Nauk, 448, 1981 | Zbl

[11] Hemmerling A. Kriegel K., “On searching of special classes of mazes and finite embedded graphs”, Lect. Notes Comput. Sci., 176, 1984, 291–300 | MR | Zbl

[12] Hemmerling A., “$1$-pointer automata searching finite plane graphs”, Z. Math. Logik Grundlagen Math., 32 (1986), 245–256 | DOI | MR | Zbl

[13] Hemmerling A., “Remark on the power of compass”, Lect. Notes Comput. Sci., 233, 1986, 405–413 | MR | Zbl

[14] Hemmerling A., “Three-dimensional traps and barrages for cooperating automata”, Lect. Notes Comput. Sci., 278, 1987, 197–203 | Zbl

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

[16] Hemmerling A., Labyrinth problems Labyrinth-searching abilities of automata, Teubner, Leipzig, 1989 | MR | Zbl

[17] Hemmerling A., “Pebble automata in labyrinths with rotation systems”, Z. Math. Logik Grundlagen Math., 37 (1991), 453–466 | DOI | MR | Zbl

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

[19] Hoffmann F., 1-Kiesel-Automaten in Labyrinthen, Report R-Math-06/82, Adw. der DDR, Berlin, 1982 | MR

[20] Inoue K., Takanami I, Nakamura A., “A note on two-dimensional finite automata”, Inf. Process. Lett., 7 (1978), 49–52 | DOI | MR | Zbl

[21] Inoue K., Nakamura A., “Two-dimensional finite automata and unacceptable functions”, Int. J. Comput. Math., 7 (1979), 207–213 | DOI | MR | Zbl

[22] Inoue K., Takanami I., “A note on decision problems for three-way two-dimensional finite automata”, Inform. Process. Lett., 10 (1980), 245–248 | DOI | MR | Zbl

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

[24] Kinber E. B., “Three-way automata on rectangular tapes over a one-letter alphabet”, Inform. Sci., 35 (1985), 61–77 | DOI | MR | Zbl

[25] Kriegel K., Universelle 1-Kiesel-Automaten für $k$-komponentige Labyrinthe, Report R-Math-04/84, Adw. der DDR, Berlin, 1984 | MR

[26] Kozen D., “Automata and planar graphs”, Fundamentals of Computation Theory, Akademie, Berlin, 1979, 243–254 | MR

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

[28] Milgram D. L., Rosenfeld A., “Array automata and array grammars”, IFIP Congress 71, North-Holland, Amsterdam, 1971, 69–74 | MR

[29] Milgram D. L., “A region crossing problem for array-bounded automata”, Inform. and Control, 31 (1976), 147–152 | DOI | MR | Zbl

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

[31] Mylopoulus J., “On the application of formal languages and automata theory to pattern recognition”, Pattern Recognition, 4 (1974), 37–51 | DOI | MR

[32] Rollik H. A., “Automaten in planaren Graphen”, Acta Inf., 13 (1980), 287–298 | DOI | MR | Zbl

[33] Savitch W., “Relations between nondeterministic and deterministic tape complexities”, J. Comput. System Sci., 4 (1970), 177–192 | MR | Zbl

[34] Savitch W., “Maze recognizing automata and nondeterministic tape complexity”, J. Comput. System Sci., 7 (1973), 389–403 | DOI | MR | Zbl

[35] Shah N. A., “Pebble automata on arrays”, Computer Graphics and Image Processing, 3 (1974), 236–246 | DOI | MR

[36] Szepietowski A., “A finite 5-pebble-automaton can search every maze”, Inform. Process. Lett., 15 (1982), 199–204 | DOI | MR | Zbl

[37] Szepietowski A., “On searching plane labyrinths by 1-pebble automata”, Elektron. Inform.-verarb. Kybernetik, 19 (1983), 79–84 | MR | Zbl

[38] Szepietowski A., “Remarks on searching labyrinths by automata”, Lect. Notes Comput. Sci., 158, 1983, 457–464 | MR | Zbl

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

[40] Andzhans A. V., “O vozmozhnostyakh avtomatov pri obkhode odnomernykh oblastei”, Latv. matem. ezhegodnik, 27, 1983, 191–201

[41] Andzhans A. V., “Vozmozhnosti avtomatov pri obkhode ploskosti.”, Problemy peredachi informatsii, 19:3 (1983), 78–89 | MR

[42] Andzhans A. V., “Slozhnost opredeleniya avtomatom ego raspolozheniya otnositelno zamknutogo kontura”, Matematicheskaya logika, matematicheskaya lingvistika i teoriya avtomatov, Kalininskii gos. un-t, Kalinin, 1983, 88–90

[43] Andzhans A. V., “O vozmozhnostyakh avtomatov pri obkhode prostranstva”, Mezhvuz. sb. rabot po teorii avtomatov, algebre i teorii chisel, Riga, 1984, 3–17

[44] Andzhans A. V., Povedenie determinirovannykh i veroyatnostnykh avtomatov v labirintakh, Diss. kand. fiz.-mat. nauk, Riga, 1987

[45] Grunskaya V. I., O vzaimodeistvii avtomatov tipa khischnik–zhertva, Diplomnaya rabota, MGU, 1988

[46] Grunskaya V. I., “O dinamicheskom vzaimodeistvii avtomatov”, Matematicheskaya kibernetika i ee prilozheniya k biologii, Izd-vo MGU, Moskva, 1987, 8–18

[47] Grunskaya V. I., Trudy mezhdunarodnoi konferentsii po intellektualnym sistemam, Moskva, 1994

[48] Grunskii I. S., Oleinik R. I., “Ob otlichimosti initsialnykh avtomatnykh labirintov konechnymi avtomatami”, Intellektualnye sistemy, 4 (1999), 273–283

[49] Kilibarda G., “Ob obkhode konechnykh labirintov sistemami avtomatov”, Diskretnaya matematika, 2:2 (1990), 71–81 | MR | Zbl

[50] Kilibarda G., “O slozhnosti avtomatnogo obkhoda labirintov”, Diskretnaya matematika, 5:3 (1993), 116–124 | MR | Zbl

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

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

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

[54] Kilibarda G., Kudryavtsev V. B., Ushchumlich Sh., “Nezavisimye sistemy avtomatov v labirintakh”, Diskretnaya matematika, 15:2 (2003), 3–39 | Zbl

[55] Klini C., “Predstavlenie sobytii v nervnykh setyakh i konechnykh avtomatakh”, Avtomaty, IL, Moskva, 1956, 15–67

[56] Kudryavtsev V. B., Ushchumlich Sh., Kilibarda G., “O povedenii avtomatov v labirintakh”, Diskretnaya matematika, 4:3 (1993), 3–26 | MR

[57] Kudryavtsev G. Yu., “O vremeni resheniya labirintnoi zadachi konechnymi avtomatami”, Sb. nauchn. trudov MEI, 138 (1987), 14–18

[58] Kudryavtsev G. Yu., “O vremeni obkhoda labirintov bez tsiklov konechnymi avtomatami”, Materialy 2-go Vsesoyuznogo seminara po diskretnoi matematike i ee prilozheniyam, Izd-vo MGU, Moskva, 1988, 202–208

[59] Kudryavtsev G. Yu., O slozhnosti konechnykh avtomatov, reshayuschikh zadachu o labirinte, Dep. v VINITI, 4.05.88, 3430–V88

[60] Kudryavtsev G. Yu., “O slozhnosti konechnykh avtomatov, reshayuschikh labirintnuyu zadachu”, Algebro-logicheskie konstruktsii. Mezhvuz. temat. sb. trudov, Kalininskii gos. un-t, Kalinin, 1989, 68–71 | Zbl

[61] Kudryavtsev G. Yu., “O vremeni obkhoda labirintov konechnymi avtomatami”, Mezhvuz. sb. trudov, Saratovskii gos. un-t, Saratov, 1989, 95–105 | MR

[62] Kudryavtsev G. Yu., O slozhnosti eksperimentov s konechnymi grafami, Dep. v VINITI 20.11.89, 6961–V89

[63] Kudryavtsev G. Yu., O vremeni resheniya labirintnykh zadach konechnymi avtomatami, Diss. kand. fiz.-mat. nauk, Saratov, 1990

[64] Kudryavtsev G. Yu., “Ob otlichimosti vershin avtomatnykh labirintov konechnymi avtomatami”, Diskretnaya matematika, 3:4 (1991), 143–152 | MR | Zbl

[65] Kudryavtsev G. Yu., “O dline testovykh avtomatno realizuemykh eksperimentov s avtomatnymi labirintami”, Diskretnaya matematika, 4:3 (1992), 86–100 | MR | Zbl

[66] Kudryavtsev G. Yu., “O vremeni resheniya labirintnykh problem konechnymi avtomatami”, Dokl. RAN, 326 (1992), 601–604 | Zbl

[67] Kurdyumov G. L., “Kollektiv avtomatov s universalnoi prokhodimostyu”, Problemy peredachi informatsii, 17:4 (1981), 98–112 | MR | Zbl

[68] Stamatovich B., Raspoznavanie spetsialnykh klassov $\pi$-labirintov avtomatami, Diss. dokt. fiz.-matem. nauk, Matem. f-t, Belgrad, 1999

[69] Stamatovich B., “Raspoznavanie odnosvyaznykh tsifr avtomatom”, Intellektualnye sistemy, 3 (1998)

[70] Stamatovich B., “Raspoznavanie dvusvyaznykh tsifr kollektivami avtomatov”, Intellektualnye sistemy, 4 (1998), 321–337

[71] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, t. 1, Mir, Moskva, 1984