Name
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). |
Year | Venue | Field |
|---|---|---|
2018 | MFCS | Integer,Discrete mathematics,Combinatorics,Exponential function,Parallelogram,Polynomial,Computer science,Automaton,Finite-state machine,Geometric shape,Robot |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Gmyr | 1 | 79 | 9.70 |
| Kristian Hinnenthal | 2 | 1 | 2.05 |
| Irina Kostitsyna | 3 | 33 | 18.08 |
| Fabian Kuhn | 4 | 2709 | 150.17 |
| Dorian Rudolph | 5 | 0 | 0.68 |
| Christian Scheideler | 6 | 1729 | 152.71 |