Graph exploration by a finite automaton

DOI10.1007/978-3-540-28629-5_34MaRDI QIDQ5311120zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg

Publication date 22 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99679

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph exploration by a finite automaton
• Automata, Languages and Programming
• Label-guided graph exploration by a finite automaton
• scientific article; zbMATH DE number 7604432
• scientific article; zbMATH DE number 3858446
• Graph automata
• Recognition of graphs by automata
• Finite automata on directed graphs
• Graph representation functions computable by finite automata

Cited in

(25)

• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Building a nest by an automaton
• Traversal of an unknown directed graph by a finite robot
• Time and space optimality of rotor-router graph exploration
• Simple agents learn to find their way: an introduction on mapping polygons
• Graph exploration by a finite automaton
• Optimal constrained graph exploration
• Visual exploration of generation algorithms for finite automata on the web
• Exploring an infinite space with finite memory scouts
• Tree exploration with little memory
• scientific article; zbMATH DE number 2119714 (Why is no real title available?)
• Label-guided graph exploration by a finite automaton
• Building a nest by an automaton
• Collaboration without communication: evacuating two robots from a disk
• STACS 2004
• Structural Information and Communication Complexity
• Automata, Languages and Programming
• Graph exploration by a deterministic memoryless automaton with pebbles
• Exploration of convex terrains by a deterministic automaton with pebbles
• Busy agents on a line
• Efficient shape formation by 3D hybrid programmable matter: an algorithm for low diameter intermediate structures
• Exploring wedges of an oriented grid by an automaton with pebbles
• Graph automata: Natural expression of self-reproduction
• Setting port numbers for fast graph exploration
• Impact of memory size on graph exploration capability

This page was built for publication: Graph exploration by a finite automaton

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311120)