Cite this article as:
Kurganskyy A. N., Sapunov S. V. On the Directional Movement of a Collective of Automata without a Compass on a One-dimensional Integer Lattice. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2016, vol. 16, iss. 3, pp. 356-365. DOI: https://doi.org/10.18500/1816-9791-2016-16-3-356-365
On the Directional Movement of a Collective of Automata without a Compass on a One-dimensional Integer Lattice
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.
1. Gasanov E. E., Kudryavtsev V. B. Teoriya hraneniya i poiska informatsii [The theory of information storage and retrieval]. Moscow, Fizmatlit, 2002, 288 p. (in Russian).
2. Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A., Lutskiy G. M. Lektsii po diskretnoy matematike [Lectures on discrete mathematics]. Saint Petersburg, BHV-Petersburg, 2004, 624 p. (in Russian).
3. Novikov D. A. Cybernetics: From Past to Future. Springer, 2016. 115 p.
4. Kline R. R. The Cybernetics Moment : Or Why We Call Our Age the Information Age. Baltimore, Maryland : Johns Hopkins Univ. Press, 2015. 352 p.
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. N. Y. : Josiah Macy Jr. Foundation, 1952. P. 169–181.
6. Glushkov V. M., Letichevsky A. A. Teoriya diskretnyih preobrazovateley [The theory of discrete converters]. Izbrannyie voprosyi algebryi i logiki [Selected problems of algebra and logic]. Novosibirsk, Nauka, 1973, pp. 5–39 (in Russian).
7. Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S. Vvedenie v teoriyu avtomatov [Introduction to Automata Theory]. Moscow, Nauka, 1985, 320 p. (in Russian).
8. Kilibarda G., Kudryavtsev V. B., Uscumli S. Inde-pendent systems of automata in labyrinths. Discrete Math. and Appl., 2003, vol. 13, iss. 3, pp. 221–255. DOI: https://doi.org/10.1515/156939203322385847.
9. Kilibarda G., Kudryavtsev V. B., Uscumli S. Collectives of automata in labyrinths. Discrete Math. and Appl., 2003, vol. 13, iss. 5, pp. 429–466. DOI: https://doi.org/10.1515/156939203322694736.
10. Stamatovich B. Recognizing simply connected numerals by automata. Intelligent systems, 1998, vol. 3, iss. 3–4, pp. 281–305 (in Russian).
11. Stamatovich B. Recognizing doubly connected numerals by collectives of automata. Intelligent systems, 1998, vol. 4, iss. 1–2, pp. 321–337 (in Russian).
12. Deglina Yu. B., Kozlovskii V. A., Kostogryz K. A. Automata recognition of digitized polygons. Artificial Intelligence, 2004, no. 3, pp. 443–452 (in Russian).
13. Dudek G., Jenkin M. Computational Principles of Mobile Robotics. Cambridge : Cambridge Univ. Press, 2010, 406 p.
14. Blum M., Kozen D. On the Power of the Compass // SFCS ’78 Proc. 19th Annu. Symp. Found. Comput. Sci. IEEE Computer Society Washington, 1978. P. 132–142. DOI: https://doi.org/10.1109/SFCS.1978.30.
15. Donald B. R. The Compass That Steered Robotics // Logic and Program Semantics. Springer, 2012. P. 50–65. DOI: https://doi.org/10.1007/978-3-642-29485-3-5.
16. Bhatt S., Even S., Greenberg D., Tayar R. Traversing Directed Eulerian Mazes // J. Graph Algorithms and Appl. 2002. Vol. 6, № 2. P. 157–173. DOI: https://doi.org/10.7155/jgaa.00049
17. Babichev A. V. Orientation in a maze. Automation and Remote Control, 2008, vol. 69, iss. 2, pp. 299– 309. DOI: https://doi.org/10.1134/S0005117908020100.
