Shape recognition by a finite automaton robot

Robert Gmyr, Kristian Hinnenthal, I. Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler

Onderzoeksoutput: Bijdrage aan congresAbstract

10 Downloads (Pure)


Motivated by the problem of shape recognition by nanoscale computing agents, we investigate the problem of detecting the geometric shape of a structure composed of hexagonal tiles by a finite-state automaton robot. In particular, in this paper we consider the question of recognizing whether the tiles are assembled into a parallelogram whose longer side has length l = f(h), for a given function f(*), where h is the length of the shorter side. To determine the computational power of the finite-state automaton robot, we identify functions that can or cannot be decided when the robot is given a certain number of pebbles. We show that the robot can decide whether l = ah+b for constant integers a and b without any pebbles, but cannot detect whether l = f(h) for any function f(x) = omega(x). For a robot with a single pebble, we present an algorithm to decide whether l = p(h) for a given polynomial p(*) of constant degree. We contrast this result by showing that, for any constant k, any function f(x) = omega(x^(6k + 2)) cannot be decided by a robot with k states and a single pebble. We further present exponential functions that can be decided using two pebbles. Finally, we present a family of functions f_n(*) such that the robot needs more than n pebbles to decide whether l = f_n(h).
Originele taal-2Engels
Aantal pagina's6
StatusGepubliceerd - 2018
Evenement34th European Workshop on Computational Geometry (EuroCG2018) - Berlin, Duitsland
Duur: 21 mrt 201823 mrt 2018


Congres34th European Workshop on Computational Geometry (EuroCG2018)
Verkorte titelEuroCG2018
Internet adres


Citeer dit

Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., & Scheideler, C. (2018). Shape recognition by a finite automaton robot. 73:1-73:6. Abstract van 34th European Workshop on Computational Geometry (EuroCG2018), Berlin, Duitsland.