RUS  ENG
Full version
JOURNALS // Izvestiya of Saratov University. Mathematics. Mechanics. Informatics // Archive

Izv. Saratov Univ. Math. Mech. Inform., 2016 Volume 16, Issue 3, Pages 356–365 (Mi isu655)

This article is cited in 3 papers

Computer Sciences

On the directional movement of a collective of automata without a compass on a one-dimensional integer lattice

O. M. Kurganskyya, S. V. Sapunovb

a State Institution «Institute of Applied Mathematics and Mechanics», 74, Rosa Luxemburg st., 83114, Donetsk, Ukraine
b Institute of Applied Mathematics and Mechanics of NAS of Ukraine, 1, Dobrovolskogo st., 84100, Slavyansk, Donetskaya obl., Ukraine

Abstract: 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.

Key words: collectives of automata, labyrinth, unidirectional movement.

UDC: 519.7

DOI: 10.18500/1816-9791-2016-16-3-356-365



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024