Shape recognition by a finite automaton robot

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
25 Downloads (Pure)

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

Original languageEnglish
Title of host publication43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
EditorsIgor Potapov, James Worrell, Paul Spirakis
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages52:1-52:15
Number of pages15
ISBN (Print)978-3-95977-086-6
DOIs
Publication statusPublished - 1 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume117

Keywords

  • Computational geometry
  • Finite automata
  • Shape recognition

Fingerprint Dive into the research topics of 'Shape recognition by a finite automaton robot'. Together they form a unique fingerprint.

Cite this