License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.52
URN: urn:nbn:de:0030-drops-96347
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9634/
Go to the corresponding LIPIcs Volume Portal

Gmyr, Robert ; Hinnenthal, Kristian ; Kostitsyna, Irina ; Kuhn, Fabian ; Rudolph, Dorian ; Scheideler, Christian

Shape Recognition by a Finite Automaton Robot

pdf-format:
LIPIcs-MFCS-2018-52.pdf (0.4 MB)

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 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).

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:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9634},
  URN =		{urn:nbn:de:0030-drops-96347},
  doi =		{10.4230/LIPIcs.MFCS.2018.52},
  annote =	{Keywords: finite automata, shape recognition, computational geometry}
}

Keywords: finite automata, shape recognition, computational geometry
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI