Graph exploration by a finite automaton
From MaRDI portal
Publication:2575752
Recommendations
Cites work
- 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?)
- Automata and Labyrinths
- Automaten in planaren Graphen
- Bounds on Universal Sequences
- Exploring Unknown Environments
- Exploring Unknown Undirected Graphs
- Exploring an unknown graph
- How to learn an unknown environment. I
- 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
(73)- Exploring an infinite space with finite memory scouts
- Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots
- Reversibility of computations in graph-walking automata
- Label-guided graph exploration by a finite automaton
- The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
- An improved lower bound for competitive graph exploration
- A general lower bound for collaborative tree exploration
- Distributed graph searching with a sense of direction
- scientific article; zbMATH DE number 2119714 (Why is no real title available?)
- Graph automata: Natural expression of self-reproduction
- Building a nest by an automaton
- A probabilistic model for the interaction of an agent with a network environment
- State complexity of transforming graph-walking automata to halting, returning and reversible
- Ping pong in dangerous graphs: optimal black hole search with pebbles
- Fault-tolerant dispersion of mobile robots
- Two-agent tree evacuation
- Black hole search in dynamic cactus graph
- Chaotic traversal (CHAT): very large graphs traversal using chaotic dynamics
- Derandomizing random walks in undirected graphs using locally fair exploration strategies
- Robustness of the rotor-router mechanism
- Graph exploration by a deterministic memoryless automaton with pebbles
- Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
- An improved strategy for exploring a grid polygon
- Collaborative exploration of trees by energy-constrained mobile robots
- Black hole search in directed graphs
- Dispersion of mobile robots on directed anonymous graphs
- Time and space optimality of rotor-router graph exploration
- Memory Efficient Anonymous Graph Exploration
- Exploring a Dynamic Ring Without Landmark
- Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
- Homomorphisms and inverse homomorphisms on graph-walking automata
- Fast periodic graph exploration with constant memory
- LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS
- Connected reconfiguration of lattice-based cellular structures by finite-memory robots
- Distributed exploration of dynamic rings
- More efficient periodic traversal in anonymous undirected graphs
- Efficient live exploration of a dynamic ring with mobile robots
- How many ants does it take to find the food?
- Exploring an unknown dangerous graph with a constant number of tokens
- Tree exploration with little memory
- Mathematical Foundations of Computer Science 2004
- Time optimal algorithms for black hole search in rings
- A time to cast away stones
- scientific article; zbMATH DE number 1775633 (Why is no real title available?)
- Homomorphisms on graph-walking automata
- Exploring a dynamic ring without landmark
- Structural Information and Communication Complexity
- Exploration of dynamic networks: tight bounds on the number of agents
- Lower and upper competitive bounds for online directed graph exploration
- Shape recognition by a finite automaton robot
- Collision-free network exploration
- STACS 2004
- Exploration of High-Dimensional Grids by Finite State Machines
- Exploration of High-Dimensional Grids by Finite Automata
- Exploration of Time-Varying Connected Graphs with Silent Agents
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
- On defining linear orders by automata
- Recognition of graphs by automata
- Distributed chasing of network intruders
- Anonymous graph exploration without collision by mobile robots
- Traversal of an unknown directed graph by a finite robot
- On the Power of Local Orientations
- Graph decomposition for memoryless periodic exploration
- Tight bounds for deterministic high-dimensional grid exploration
- Wireless evacuation on \(m\) rays with \(k\) searchers
- Automata, Languages and Programming
- Collaborative Exploration by Energy-Constrained Mobile Robots
- Evacuation of equilateral triangles by mobile agents of limited communication range
- Fast dispersion of mobile robots on arbitrary graphs
- scientific article; zbMATH DE number 7525472 (Why is no real title available?)
- Impact of memory size on graph exploration capability
- State complexity of union and intersection on graph-walking automata
- Graph Decomposition for Improving Memoryless Periodic Exploration
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)
