<p><a href="https://ieeexplore.ieee.org/document/4567972" rel="nofollow noreferrer">Blum and Kozen</a> have shown that a robot with the computational capabilities of a finite automaton can visit all <span class="math-container">$n$</span> cells in a quadratic maze when the robot is equipped with two pebbles which it may place at any cell. Alternatively, <span class="math-container">$\Omega(\log(n))$</span> memory (and no pebbles) is also sufficient. They did not analyse their algorithm's runtime, but I suspect the execution requires <span class="math-container">$\Omega(n^2)$</span> steps without pebbles and <span class="math-container">$\Omega(n^3)$</span> with pebbles.</p>
<p><strong>My question:</strong> Is linear-time exploration (under the same memory/pebble requirements) possible? If yes, how? If not, why not?</p>

CC BY-SA 4.0
2023-05-24T06:39:07.873Z
What research have you done?  Have you done a literature review of papers that cite Blum & Kozel, by searching on Google Scholar?  If there is an improvement on their result, it seems likely such a paper would cite them.
D.W.
CC BY-SA 4.0
2023-06-10T15:53:16.497Z
@D.W. I seem to have missed your comment, sorry. I did search for papers that cite Blum & Kozen, but I couldn't find any runtime improvements, which is why I turned to Stack Exchange. [This related paper](https://cpsc.yale.edu/sites/default/files/files/tr1188.pdf) from 1999 lists the task of finding an algorithm for visiting all cells of a maze that requires "substantially less than $O(n^2)$ moves" as an open question, so I'm not too optimistic. But at the same time, I haven't found any evidence that $O(n^2)$ is a lower bound for this type of problem.
jfriemel
<graph-algorithms><automata-theory>
Linear-time maze exploration for finite automaton with pebbles?
jfriemel
# Linear-time maze exploration for finite automaton with pebbles?

(Asked by: username_0 on 2023-05-23)

[Blum and Kozen](https://ieeexplore.ieee.org/document/4567972) have shown that a robot with the computational capabilities of a finite automaton can visit all $n$ cells in a quadratic maze when the robot is equipped with two pebbles which it may place at any cell. Alternatively, $\Omega(\log(n))$ memory (and no pebbles) is also sufficient. They did not analyse their algorithm's runtime, but I suspect the execution requires $\Omega(n^2)$ steps without pebbles and $\Omega(n^3)$ with pebbles.

**My question:** Is linear-time exploration (under the same memory/pebble requirements) possible? If yes, how? If not, why not?

**Tags:** graph-algorithms, automata-theory

> **Comments:**
> **username_1**: What research have you done?  Have you done a literature review of papers that cite Blum & Kozel, by searching on Google Scholar?  If there is an improvement on their result, it seems likely such a paper would cite them.  
> **username_0**: @username_1 I seem to have missed your comment, sorry. I did search for papers that cite Blum & Kozen, but I couldn't find any runtime improvements, which is why I turned to Stack Exchange. [This related paper](https://cpsc.yale.edu/sites/default/files/files/tr1188.pdf) from 1999 lists the task of finding an algorithm for visiting all cells of a maze that requires "substantially less than $O(n^2)$ moves" as an open question, so I'm not too optimistic. But at the same time, I haven't found any evidence that $O(n^2)$ is a lower bound for this type of problem.  

---

## 0 answers

