FRAIGNIAUD, Pierre; ILCINKAS, David; PELC, Andrzej

doi:10.1016/j.dam.2007.11.001

Métadonnées

Licence d’utilisation du document

FRAIGNIAUD, Pierre
Laboratoire d'informatique Algorithmique : Fondements et Applications [LIAFA]

ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

PELC, Andrzej
Département d'Informatique et d'Ingénierie [DII]

Langue

Article de revue

Ce document a été publié dans

Discrete Applied Mathematics. 2008-06, vol. 156, n° 12, p. 2310-2319

Elsevier

Résumé en anglais

A mobile agent (robot), modeled as a finite automaton, has to visit all nodes of a regular graph. How does the memory size of the agent (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable an agent to explore more graphs? We give a partial answer to this problem by showing that a strict gain of the exploration power can be obtained by a polynomial increase of the number of states. We also show that, for automata with few states, the increase of memory by even one state results in the capability of exploring more graphs.< Réduire

Mots clés en anglais

Graph exploration

finite automaton

memory size

mobile agent

robot

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198618

DOI

http://dx.doi.org/10.1016/j.dam.2007.11.001

Project ANR

Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322

Origine

Importé de hal

Unités de recherche

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800