Graph exploration by a finite automaton
From MaRDI portal
Publication:2575752
Recommendations
Cites work
- Automata and Labyrinths
- Automaten in planaren Graphen
- Bounds on Universal Sequences
- Exploring an unknown graph
- Exploring Unknown Environments
- Exploring Unknown Undirected Graphs
- How to learn an unknown environment. I
- scientific article; zbMATH DE number 3673535 (Why is no real title available?)
- scientific article; zbMATH DE number 3696506 (Why is no real title available?)
- scientific article; zbMATH DE number 3722098 (Why is no real title available?)
- scientific article; zbMATH DE number 194193 (Why is no real title available?)
- scientific article; zbMATH DE number 3554185 (Why is no real title available?)
- scientific article; zbMATH DE number 3564881 (Why is no real title available?)
- scientific article; zbMATH DE number 3633728 (Why is no real title available?)
- scientific article; zbMATH DE number 3348082 (Why is no real title available?)
- scientific article; zbMATH DE number 3356673 (Why is no real title available?)
- LATIN 2004: Theoretical Informatics
- Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
- Lower bounds on universal traversal sequences based on chains of length five
- Mathematical Foundations of Computer Science 2004
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Navigating in Unfamiliar Geometric Terrain
- On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
- Online Navigation in a Room
- Optimal constrained graph exploration
- Piecemeal graph exploration by a mobile robot.
- Pseudorandom generators for space-bounded computation
- Pseudorandomness for network algorithms
- STACS 2004
- The power of a pebble: Exploring and mapping directed graphs
- Tree exploration with little memory
- Universal sequences for complete graphs
- Universal traversal sequences for expander graphs
- Universal traversal sequences for paths and cycles
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
Cited in
(80)- Recognition of graphs by automata
- State complexity of union and intersection on graph-walking automata
- Dispersion of mobile robots on directed anonymous graphs
- Two-agent tree evacuation
- Homomorphisms on graph-walking automata
- Exploring a dynamic ring without landmark
- Distributed exploration of dynamic rings
- On defining linear orders by automata
- Reversibility of computations in graph-walking automata
- Building a nest by an automaton
- Exploration of dynamic networks: tight bounds on the number of agents
- Distributed graph searching with a sense of direction
- Traversal of an unknown directed graph by a finite robot
- Collision-free network exploration
- Time and space optimality of rotor-router graph exploration
- The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
- Robustness of the rotor-router mechanism
- Ping pong in dangerous graphs: optimal black hole search with pebbles
- Graph decomposition for memoryless periodic exploration
- State complexity of transforming graph-walking automata to halting, returning and reversible
- A probabilistic model for the interaction of an agent with a network environment
- Time optimal algorithms for black hole search in rings
- Chaotic traversal (CHAT): very large graphs traversal using chaotic dynamics
- Graph Decomposition for Improving Memoryless Periodic Exploration
- More efficient periodic traversal in anonymous undirected graphs
- Black hole search in directed graphs
- An improved strategy for exploring a grid polygon
- Lower and upper competitive bounds for online directed graph exploration
- Collaborative Exploration by Energy-Constrained Mobile Robots
- On the Power of Local Orientations
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
- scientific article; zbMATH DE number 1775633 (Why is no real title available?)
- 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 WITH ADJUSTABLE RATIO OF LABELS
- Label-guided graph exploration by a finite automaton
- Shape recognition by a finite automaton robot
- Building a nest by an automaton
- Exploration of High-Dimensional Grids by Finite Automata
- Exploration of Time-Varying Connected Graphs with Silent Agents
- Memory Efficient Anonymous Graph Exploration
- STACS 2004
- Mathematical Foundations of Computer Science 2004
- Structural Information and Communication Complexity
- Automata, Languages and Programming
- Connected reconfiguration of lattice-based cellular structures by finite-memory robots
- Wireless evacuation on \(m\) rays with \(k\) searchers
- A general lower bound for collaborative tree exploration
- Homomorphisms and inverse homomorphisms on graph-walking automata
- Efficient live exploration of a dynamic ring with mobile robots
- Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
- Fault-tolerant dispersion of mobile robots
- Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
- A time to cast away stones
- Exploring a Dynamic Ring Without Landmark
- Exploration of High-Dimensional Grids by Finite State Machines
- Tight bounds for deterministic high-dimensional grid exploration
- Evacuation of equilateral triangles by mobile agents of limited communication range
- Fast dispersion of mobile robots on arbitrary graphs
- Black hole search in dynamic cactus graph
- Graph exploration by a deterministic memoryless automaton with pebbles
- Derandomizing random walks in undirected graphs using locally fair exploration strategies
- Efficient dispersion in triangular grids without prior knowledge
- Graph exploration: the impact of a distance constraint
- A time to cast away stones: on a family of pebble automata
- Fault-tolerant dispersion of mobile robots
- Dispersion of mobile robots on graphs in the asynchronous model
- Near-optimal dispersion on arbitrary anonymous graphs
- Graph automata: Natural expression of self-reproduction
- Collaborative exploration of trees by energy-constrained mobile robots
- Lower bounds for graph-walking automata
- Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots
- An improved lower bound for competitive graph exploration
- How many ants does it take to find the food?
- Exploring an unknown dangerous graph with a constant number of tokens
- Distributed chasing of network intruders
- Fast periodic graph exploration with constant memory
- Impact of memory size on graph exploration capability
- Anonymous graph exploration without collision by mobile robots
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 Q2575752)
