2026-08-16T20:49:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9634 2024-03-06T10:44:35Z ddc:004 open_access

Shape Recognition by a Finite Automaton Robot Gmyr, Robert Hinnenthal, Kristian Kostitsyna, Irina Kuhn, Fabian Rudolph, Dorian Scheideler, Christian finite automata shape recognition computational geometry 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Gmyr and Kristian Hinnenthal and Irina Kostitsyna and Fabian Kuhn and Dorian Rudolph and Christian Scheideler 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.52 urn:nbn:de:0030-drops-96347 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.52 eng https://creativecommons.org/licenses/by/3.0/legalcode