TY - GEN

T1 - Shape recognition by a finite automaton robot

AU - Gmyr, Robert

AU - Hinnenthal, Kristian

AU - Kostitsyna, Irina

AU - Kuhn, Fabian

AU - Rudolph, Dorian

AU - Scheideler, Christian

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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 ` = 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 ` = ah+ b for constant integers a and b without any pebbles, but cannot detect whether ` = f(h) for any function f(x) = ω(x). For a robot with a single pebble, we present an algorithm to decide whether ` = 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) = ω(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 ` = f
n(h).

AB - 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 ` = 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 ` = ah+ b for constant integers a and b without any pebbles, but cannot detect whether ` = f(h) for any function f(x) = ω(x). For a robot with a single pebble, we present an algorithm to decide whether ` = 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) = ω(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 ` = f
n(h).

KW - Computational geometry

KW - Finite automata

KW - Shape recognition

UR - http://www.scopus.com/inward/record.url?scp=85053216096&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2018.52

DO - 10.4230/LIPIcs.MFCS.2018.52

M3 - Conference contribution

SN - 978-3-95977-086-6

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 52:1-52:15

BT - 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018

A2 - Potapov, Igor

A2 - Worrell, James

A2 - Spirakis, Paul

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl, Germany

ER -