H. Antelmann, Ober den Platzbedarf von Fallen f ur endliche Automaten, 1980.

G. Asser, Bemerkungen zum labyrinth problem, Elektr. Inform. und Kybern. (EIK), vol.13, issue.3-4, pp.203-216, 1977.

M. Blum and C. Hewitt, Automata on a 2-dimensional tape, 8-th IEEE Conference on Swat, pp.155-160, 1967.

M. Blum and D. Kozen, On the power of the compass, 19-th IEEE FOCS Conference, pp.132-142, 1978.

M. Blum and W. J. Sakoda, On the capability of nita automata in 2 and 3 dimensional space, 17-th IEEE FOCS Conference, pp.147-161, 1977.

L. Budach, On the solution of the labyrinth problem for nite automata, Elektr. Inform. und Kybern. (EIK), vol.11, pp.661-672, 1975.

L. Budach, Environments, labyrinths and automata, Proceedings of Foundations of Computation Theory (FCT'77), vol.56, pp.54-64, 1977.

L. Budach, Automata and labyrinths, Math. Nachr, vol.86, pp.195-282, 1978.

L. Budach, Two pebbles don't suuce, MFCS'81, vol.118, pp.578-589, 1981.

J. H. Chang, O. H. Ibarra, and M. A. Palis, On pebble automata, Theoretical Computer Science, vol.44, pp.111-121, 1986.

J. H. Conway, Mathematical games. Scientiic American, October:120{123, 1970.

J. H. Conway, Mathematical games. Scientiic American, 1971.

R. Cori and . Cartes, hypercartes et leurs groupes d'automorphismes. S eminaire Lotharingien, 1984.

W. Coy, On mice and maze, Elektr. Inform. und Kybern. (EIK), vol.14, pp.227-232, 1978.

A. Stephen, C. W. Cook, and . Rackoo, Space lower bounds for maze threadability on restricted machines, Siam J. Comput, vol.9, pp.637-652, 1980.

M. Delorme and J. Mazoyer, Deux th eor emes d'universalit e pour des automates a galets, 1997.

]. K. Dd-op71 and . Opp, Automaten in labyrinthen, Elektr. Inform. und Kybern. (EIK), vol.7, 1971.

C. Patrick and . Fischer, Turing machines with restricted memory access, Information and Control, vol.9, pp.364-379, 1966.

, Max Garzon. Cyclic automata. Theoretical Computer Science, vol.53, pp.307-317, 1987.

, Max Garzon. Cayley automata. Theoretical Computer Science, vol.103, pp.83-102, 1993.

P. Globerman and D. Harel, Complexity results for multi-pebble automata and their logics, International Conference o n A lgorithms, Logic and Programming (ICALP94), 1994.

A. Hemmerling, 1-pointer automata searching nite plane graphs, Logik und Grundlaggen d. Math, vol.32, pp.245-256, 1986.

A. Hemmerling, Remark on the power of compass, Proceedings of Mathematical Foundation of Computer Science ( M F CS'86), vol.233, pp.405-413, 1986.

A. Hemmerling, Normed two-plane traps for nite systems of cooperating automata, Elektr. Inform. und Kybern. (EIK), vol.23, pp.453-470, 1987.

A. Hemmerling, Three dimensional traps and barrages for cooperating automata, Proceedings of Foundations of Computation Theory (FCT'87), vol.278, 1987.

A. Hemmerling, Pebble automata in labyrinths with rotation systems, Logik und Grundlaggen d. Math, pp.453-466, 1991.

A. Hemmerling and K. Kriegel, On searching of special classes of mazes and nite enbedded graphs, Proceedings of Mathematical Foundation of Computer Science ( M F CS'84), vol.176, pp.291-300, 1984.

F. Hoomann, One pebble does not suuce to search plane labyrinths, Proceedings of Foundations of Computation Theory (FCT'81), vol.117, pp.433-444, 1981.

F. Hoomann, Four pebbles don't suuce to search planar innnite labyrinths, Theory of algorithms, pp.191-206, 1985.

J. E. Hopcroft and J. D. Ullmann, Introduction to Automata Theory, Languages and Computation

A. Jacques, Constellations et graphes topologiques. Combinatorial Theory and its Applications, 1970.
URL : https://hal.archives-ouvertes.fr/tel-01591126

D. Kozen, Automata and planar graphs, Proceedings of Foundations of Computation Theory (FCT'79), pp.243-254, 1979.

K. Kriegel, Universelle-1-Kiesel-Automaten f ur k-komponentige Labyrinthe, 1984.

P. Lienhardt, Subdivisions de surfaces et cartes bidimensionnelles, 1989.

B. Leong and J. Seiferas, New real-time simulation of multihead tape units, Journal of Assocation for Computing Machinery (JACM), vol.28, pp.166-180, 1981.

A. R. Meyer and M. J. Fischer, Economy of description by automata, grammars and formal systems, 21st Symp. on Switching and Automata Theory, pp.188-191, 1971.

M. L. Minsky, Finite and Innnte Machines. P r e n tice Hall, 1967.

]. H. M-ul79 and . Uller, Automata catching labyrinths with at most three components, Elektr. Inform. und Kybern. (EIK), vol.15, issue.1{2, pp.3-9, 1979.

J. Mylopoulos, On the recognition of topological invariants by 4 -w ay nite automata, Computer Graphics and Image Processing, vol.1, pp.308-316, 1972.

A. Goralcikova, P. Goralcik, and K. , Alternation with a pebble, Information Processing Letters, vol.38, pp.7-13, 1991.

E. Remila, Pavages de gures par des barres et reconnaissance d e graphes sous-jacents a des r eseaux d'automates, 1992.

P. Rosenstiehl, J. R. Fiksel, and A. Holliger, Intelligent graphs : Networks of nite automata capable of solving graph problems, Graph Theory and Computing, pp.219-265, 1972.

H. A. Rollik, Automaten in planaren graphen, Acta Informatica, vol.13, pp.287-298, 1980.

A. Rosenfeld, Connectivity in digital pictures, Journal of the Association for Computing Machinery, vol.17, pp.146-160, 1970.

A. Rosenfeld, Picture L anguages, 1979.

R. Ritchie and F. Springsteel, Language recognition by marking automata, Infor. and Control, vol.20, pp.313-330, 1972.

W. J. Savitch, Relations between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences, vol.4, pp.177-192, 1970.

W. J. Savitch, Maze recognizing automata and non-deterministic tape complexity, Journal of Computer and System Sciences, vol.7, pp.389-403, 1973.

C. E. Shannon, Presentation of a maze-solving machine, Cyberneticss Trans. of the 8th Conf. of the Josiah Macy Jr Foand, vol.173, 1951.

A. N. Shah, Pebble automata on arrays, Computer Graphics and Image Processing, vol.3, pp.236-246, 1974.

A. Szepietowski, A nite-5-pebble automaton can search e v ery maze, Information Processing Letter, vol.15, issue.5, pp.199-204, 1982.

A. Szepietowski, On searching plane labyrinths, Elektr. Inform. und Kybern. (EIK), vol.19, pp.79-84, 1983.

A. Szepietowski, Remarks on searching labyrinths by automata, Proceedings of Foundations of Computation Theory (FCT'83), 1983.

A. Szepietowski, On paterson's problem, Elektr. Inform. und Kybern. (EIK), vol.21, issue.6, pp.313-314, 1985.

L. Tougne, Construction de familles de cercles discrets par automates cellulaires, 1997.

G. Vijayan and A. Wigderson, Rectilinear graphs and their embeddings, SIAM Journal of Compututing, vol.14, pp.355-372, 1985.