Gmyr, Robert ;
Hinnenthal, Kristian ;
Kostitsyna, Irina ;
Kuhn, Fabian ;
Rudolph, Dorian ;
Scheideler, Christian
Shape Recognition by a Finite Automaton Robot
Abstract
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 finitestate 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 finitestate 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).
BibTeX  Entry
@InProceedings{gmyr_et_al:LIPIcs:2018:9634,
author = {Robert Gmyr and Kristian Hinnenthal and Irina Kostitsyna and Fabian Kuhn and Dorian Rudolph and Christian Scheideler},
title = {{Shape Recognition by a Finite Automaton Robot}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {52:152:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9634},
URN = {urn:nbn:de:0030drops96347},
doi = {10.4230/LIPIcs.MFCS.2018.52},
annote = {Keywords: finite automata, shape recognition, computational geometry}
}
27.08.2018
Keywords: 

finite automata, shape recognition, computational geometry 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 