Geodesic
On the directional movement of a collective of automata without a compass on a one-dimensional integer lattice
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 16 (2016) no. 3, pp. 356-365.

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

A collective of finite automata has to preserve unidirectional movement on one-dimensional integer lattice whose elements (vertices) are unlabelled. The automata does not distinguish between equally labelled vertices by their coordinates of direction (that means each automaton has no compass). We considered collectives consisting of an automaton and some pebbles, i.e. automata of the simplest form, whose positions are completely determined by automaton. We prove that a collective of automaton and a maximum of 2 pebbles cannot maintain movement direction on the one-dimensional integer lattice, but collective of automaton and 3 pebbles can. 
@article{ISU_2016_16_3_a13,
     author = {O. M. Kurganskyy and S. V. Sapunov},
     title = {On the directional movement of a collective of automata without a compass on a one-dimensional integer lattice},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {356--365},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2016_16_3_a13/}
}
TY  - JOUR
AU  - O. M. Kurganskyy
AU  - S. V. Sapunov
TI  - On the directional movement of a collective of automata without a compass on a one-dimensional integer lattice
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2016
SP  - 356
EP  - 365
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ISU_2016_16_3_a13/
LA  - ru
ID  - ISU_2016_16_3_a13
ER  - 
%0 Journal Article
%A O. M. Kurganskyy
%A S. V. Sapunov
%T On the directional movement of a collective of automata without a compass on a one-dimensional integer lattice
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2016
%P 356-365
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ISU_2016_16_3_a13/
%G ru
%F ISU_2016_16_3_a13
O. M. Kurganskyy; S. V. Sapunov. On the directional movement of a collective of automata without a compass on a one-dimensional integer lattice. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 16 (2016) no. 3, pp. 356-365. http://geodesic.mathdoc.fr/item/ISU_2016_16_3_a13/

[1] Gasanov E. E., Kudryavtsev V. B., The theory of information storage and retrieval, Fizmatlit, M., 2002, 288 pp. (in Russian)

[2] Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A., Lutskiy G. M., Lectures on discrete mathematics, BHV-Petersburg, Saint Petersburg, 2004, 624 pp. (in Russian)

[3] Novikov D. A., Cybernetics: From Past to Future, Springer, 2016, 115 pp.

[4] Kline R. R., The Cybernetics Moment: Or Why We Call Our Age the Information Age, Johns Hopkins Univ. Press, Baltimore, Maryland, 2015, 352 pp.

[5] Shannon Cl. E., “Presentation of a maze-solving machine”, Cybernetics: Circular, Causal and Feedback Mechanisms in Biological and Social Systems, Transactions of VIII Conference, Josiah Macy Jr. Foundation, N. Y., 1952, 169–181

[6] Glushkov V. M., Letichevsky A. A., “The theory of discrete converters”, Selected problems of algebra and logic, Nauka, Novosibirsk, 1973, 5–39 (in Russian)

[7] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Introduction to Automata Theory, Nauka, M., 1985, 320 pp. (in Russian)

[8] Kilibarda G., Kudryavtsev V. B., Ušćumlić Š., “Independent systems of automata in labyrinths”, Discrete Math. and Appl., 13:3 (2003), 221–255 | DOI | MR | Zbl

[9] Kilibarda G., Kudryavtsev V. B., Ušćumlić Š., “Collectives of automata in labyrinths”, Discrete Math. and Appl., 13:5 (2003), 429–466 | DOI | MR | Zbl

[10] Stamatovich B., “Recognizing simply connected numerals by automata”, Intelligent systems, 3:3–4 (1998), 281–305 (in Russian)

[11] Stamatovich B., “Recognizing doubly connected numerals by collectives of automata”, Intelligent systems, 4:1–2 (1998), 321–337 (in Russian) | Zbl

[12] Deglina Yu. B., Kozlovskii V. A., Kostogryz K. A., “Automata recognition of digitized polygons”, Artificial Intelligence, 2004, no. 3, 443–452 (in Russian)

[13] Dudek G., Jenkin M., Computational Principles of Mobile Robotics, Cambridge Univ. Press, Cambridge, 2010, 406 pp. | Zbl

[14] Blum M., Kozen D., “On the Power of the Compass”, Proc. 19th Annu. Symp. Found. Comput. Sci., SFCS '78, IEEE Computer Society Washington, 1978, 132–142 | DOI | MR

[15] Donald B. R., “The Compass That Steered Robotics”, Logic and Program Semantics, Springer, 2012, 50–65 | DOI | MR | Zbl

[16] Bhatt S., Even S., Greenberg D., Tayar R., “Traversing Directed Eulerian Mazes”, J. Graph Algorithms and Appl., 6:2 (2002), 157–173 | DOI | MR | Zbl

[17] Babichev A. V., “Orientation in a maze”, Automation and Remote Control, 69:2 (2008), 299–309 | DOI | MR | Zbl