Space Lower Bounds for Maze Threadability on Restricted Machines

DOI10.1137/0209048zbMath0445.68038OpenAlexW2027188157MaRDI QIDQ3890116

Stephen A. Cook, Charles W. Rackoff

Publication date: 1980

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0209048

zbMATH Keywords

Turing machinespace lower boundspebble automatarestricted machinesmaze threadability problem

Mathematics Subject Classification ID

Related Items (33)

A type-based complexity analysis of object oriented programs ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Graph Decomposition for Improving Memoryless Periodic Exploration ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ Reachability and the power of local ordering ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Length lower bounds for reflecting sequences and universal traversal sequences ⋮ Reachability is harder for directed than for undirected finite graphs ⋮ The complexity of graph connectivity ⋮ How to meet when you forget: log-space rendezvous in arbitrary graphs ⋮ Improved length lower bounds for reflecting sequences ⋮ Graph decomposition for memoryless periodic exploration ⋮ More efficient periodic traversal in anonymous undirected graphs ⋮ Milking the Aanderaa argument ⋮ Universal sequences for complete graphs ⋮ Pebble machines and tree walking machines ⋮ Pure Pointer Programs with Iteration ⋮ Incremental branching programs ⋮ Distributed chasing of network intruders ⋮ Fast periodic graph exploration with constant memory ⋮ How much memory is needed for leader election ⋮ Setting port numbers for fast graph exploration ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space ⋮ Lower bounds on the length of universal traversal sequences ⋮ Ramified Corecurrence and Logspace ⋮ Finite graph automata for linear and boundary graph languages ⋮ Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs ⋮ Energy Consumption of Group Search on a Line ⋮ A space lower bound for \(st\)-connectivity on node-named JAGs ⋮ More Efficient Periodic Traversal in Anonymous Undirected Graphs ⋮ Voronoi-like nondeterministic partition of a lattice by collectives of finite automata

This page was built for publication: Space Lower Bounds for Maze Threadability on Restricted Machines