To the best of our knowledge, there exists no prior work on addressing the
space complexity of general tasks in the single-agent model. Nevertheless, the space
complexity of the single-agent model for a specific problem is much investigated.
The mainstream of this research line is the graph exploration problem, which
has a long history and the origin goes back to the Shannon's experiment on maze-solving mouse [1]}. In the field of theoretical computer science, it received much attention
after the seminal paper by Aleliunas et al. [2]} providing
the explicit polynomial-time upper bound of the random walks in undirected graphs
(so-called cover time). It implies that a single \(O(\log n)\) -bit counter yields
a simple randomized graph exploration algorithm with termination. This result triggers the interest of log-space deterministic graph exploration algorithms in relation to the
computational complexity issue of log-space computability, and a number of algorithms are developed [3]}, [4]}, [5]}, [6]}, [7]}. The Reingold's seminal logspace undirected connectivity algorithm is one of the milestones on this line [8]}.
The memory-size optimality of the Reingold's algorithm is also shown by Fraigniaud et al. [9]}. The speed matter of graph exploration is considered with
respect to time-space tradeoff [10]}, [11]}.
