Shape Recognition by a Finite Automaton Robot
Shape Recognition by a Finite Automaton Robot
复制标题
有限自动机机器人的形状识别
DOI：
10.4230/lipics.mfcs.2018.52
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
C. Scheideler
中科院分区：
文献类型：
--
作者：
R. Gmyr;Kristian Hinnenthal;I. Kostitsyna;F. Kuhn;Dorian Rudolph;C. Scheideler
受纳米级计算代理形状识别问题的启发，我们研究了有限状态自动机机器人检测由六边形瓷砖组成的结构的几何形状的问题。特别是，在本文中，我们考虑识别瓷砖是否组装成平行四边形的问题，对于给定函数 f(*)，其中 h 是较短边的长度，其较长边的长度为 l = f(h)。为了确定有限状态自动机机器人的计算能力，我们确定了当给机器人一定数量的卵石时可以或不能决定的函数。我们证明，对于常整数 a 和 b，机器人可以在没有任何卵石的情况下判断是否 l = ah+b，但无法检测对于任何函数 f(x) = omega(x) 是否 l = f(h)。对于具有单个卵石的机器人，我们提出了一种算法来确定对于给定的常量多项式 p(*) 是否 l = p(h)。我们对比这个结果，表明对于任何常数 k，任何函数 f(x) = omega(x^(6k + 2)) 都不能由具有 k 个状态的机器人和单个卵石来决定。我们进一步提出可以使用两个卵石来确定的指数函数。最后，我们提出了一系列函数 f_n(*)，使得机器人需要超过 n 个卵石来决定是否 l = f_n(h)。
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).