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


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Shape recognition by a finite automaton robot


    Beteiligte:
    Gmyr, Robert (Autor:in) / Hinnenthal, Kristian (Autor:in) / Kostitsyna, I. (Autor:in) / Kuhn, Fabian (Autor:in) / Rudolph, Dorian (Autor:in) / Scheideler, Christian (Autor:in)

    Erscheinungsdatum :

    01.01.2018


    Anmerkungen:

    Gmyr , R , Hinnenthal , K , Kostitsyna , I , Kuhn , F , Rudolph , D & Scheideler , C 2018 , ' Shape recognition by a finite automaton robot ' , 34th European Workshop on Computational Geometry (EuroCG2018) , Berlin , Germany , 21/03/18 - 23/03/18 pp. 73:1-73:6 .


    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629



    Automaton-Logic Methods in Pattern Recognition

    Levin, E. I. | British Library Online Contents | 1996


    Real-time context-based gesture recognition using HMM and automaton

    Iwai, Y. / Shimizu, H. / Yachida, M. | IEEE | 1999


    An Automaton-Logic Model for the Recognition of Visual Patterns

    Levin, V. I. | British Library Online Contents | 1998


    Two-Stage Allocation Model for Parking Robot Systems Using Cellular Automaton Simulation

    Ni, Xun-You / Sun, Daniel(Jian) / Zhao, Jing et al. | Transportation Research Record | 2024


    Movable Finite Automaton Models for Self-Organization of A Tail Segment in Bacteriophage T4

    Hatakeyama, T. / Bai, Y. | British Library Online Contents | 1998