Space Lower Bounds for Maze Threadability on Restricted Machines
From MaRDI portal
Publication:3890116
DOI10.1137/0209048zbMath0445.68038MaRDI QIDQ3890116
Charles W. Rackoff, Stephen A. Cook
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
Turing machine; space lower bounds; pebble automata; restricted machines; maze threadability problem
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
Related Items
Memory Efficient Anonymous Graph Exploration, Ramified Corecurrence and Logspace, More efficient periodic traversal in anonymous undirected graphs, 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, 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, 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
