Space Lower Bounds for Maze Threadability on Restricted Machines

DOI10.1137/0209048MaRDI QIDQ3890116zbMATH OpenOpenAlexFDO

Authors Stephen 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

maze threadability problempebble automatarestricted machinesspace lower boundsTuring machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(34)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3890116)