Space Lower Bounds for Maze Threadability on Restricted Machines

DOI10.1137/0209048zbMath0445.68038MaRDI 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 machine; space lower bounds; pebble automata; restricted machines; maze threadability problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68R10: Graph theory (including graph drawing) in computer science

Related Items

The complexity of graph connectivity, A Framework for In-place Graph Algorithms, Energy Consumption of Group Search on a Line, Memory Efficient Anonymous Graph Exploration, Ramified Corecurrence and Logspace, Improved length lower bounds for reflecting sequences, 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, 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