On the public citation graph
Space Lower Bounds for Maze Threadability on Restricted Machines
0 signed · 98 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1016/s0019-9958(64)90120-2openalex-snapshot
Classes of languages and linear-bounded automata
inferredcites →https://doi.org/10.1016/s0022-0000(70)80006-xopenalex-snapshot
Relationships between nondeterministic and deterministic tape complexities
inferredcites →https://doi.org/10.1016/s0022-0000(73)80031-5openalex-snapshot
Maze recognizing automata and nondeterministic tape complexity
inferredcites →https://doi.org/10.1109/sfcs.1979.34openalex-snapshot
Random walks, universal traversal sequences, and the complexity of maze problems
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.1996.0085openalex-snapshot
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata
inferred← citeshttps://doi.org/10.1006/jcss.1997.1485openalex-snapshot
Counting Quantifiers, Successor Relations, and Logarithmic Space
inferred← citeshttps://doi.org/10.1007/11602613_77openalex-snapshot
Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs
inferred← citeshttps://doi.org/10.1007/11672142_39openalex-snapshot
Nested Pebbles and Transitive Closure
inferred← citeshttps://doi.org/10.1007/11685654_1openalex-snapshot
The Reduced Automata Technique for Graph Exploration Space Lower Bounds
inferred← citeshttps://doi.org/10.1007/11780823_6openalex-snapshot
Setting Port Numbers for Fast Graph Exploration
inferred← citeshttps://doi.org/10.1007/3-540-12689-9_90openalex-snapshot
Deterministic dynamic logic of recursive programs is weaker than dynamic logic
inferred← citeshttps://doi.org/10.1007/3-540-44679-6_25openalex-snapshot
Optimizing a Computational Method for Length Lower Bounds for Reflecting Sequences
inferred← citeshttps://doi.org/10.1007/3-540-55808-x_10openalex-snapshot
The complexity of graph connectivity
inferred← citeshttps://doi.org/10.1007/3-540-57568-5_251openalex-snapshot
Time space tradeoffs (getting closer to the barrier?)
inferred← citeshttps://doi.org/10.1007/3-540-57785-8_136openalex-snapshot
Reachability and the power of local ordering
inferred← citeshttps://doi.org/10.1007/3-540-61332-3_139openalex-snapshot
Improved length lower bounds for reflecting sequences
inferred← citeshttps://doi.org/10.1007/978-3-030-91081-5_7openalex-snapshot
How Do Mobile Agents Benefit from Randomness?
inferred← citeshttps://doi.org/10.1007/978-3-319-05446-9_3openalex-snapshot
Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-24597-1_18openalex-snapshot
Randomized Time-Space Tradeoffs for Directed Graph Connectivity
inferred← citeshttps://doi.org/10.1007/978-3-540-72951-8_4openalex-snapshot
Fast Periodic Graph Exploration with Constant Memory
inferred← citeshttps://doi.org/10.1007/978-3-540-87531-4_8openalex-snapshot
Pure Pointer Programs with Iteration
inferred← citeshttps://doi.org/10.1007/978-3-540-89439-1_43openalex-snapshot
A Formalised Lower Bound on Undirected Graph Reachability
inferred← citeshttps://doi.org/10.1007/978-3-540-92248-3_2openalex-snapshot
Memory Efficient Anonymous Graph Exploration
inferred← citeshttps://doi.org/10.1007/978-3-642-03816-7_43openalex-snapshot
Graph Decomposition for Improving Memoryless Periodic Exploration
inferred← citeshttps://doi.org/10.1007/978-3-642-11476-2_14openalex-snapshot
More Efficient Periodic Traversal in Anonymous Undirected Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-15763-9_25openalex-snapshot
How Much Memory Is Needed for Leader Election
inferred← citeshttps://doi.org/10.1007/978-3-642-37075-5_21openalex-snapshot
Pure Pointer Programs and Tree Isomorphism
inferred← citeshttps://doi.org/10.1007/978-3-662-46678-0_27openalex-snapshot
The Computational Contents of Ramified Corecurrence
inferred← citeshttps://doi.org/10.1007/bf01202039openalex-snapshot
Undirecteds-t connectivity in polynomial time and sublinear space
inferred← citeshttps://doi.org/10.1007/s00224-007-9049-yopenalex-snapshot
Incremental Branching Programs
inferred← citeshttps://doi.org/10.1007/s00446-011-0131-yopenalex-snapshot
How much memory is needed for leader election
inferred← citeshttps://doi.org/10.1007/s00446-011-0141-9openalex-snapshot
How to meet when you forget: log-space rendezvous in arbitrary graphs
inferred← citeshttps://doi.org/10.1007/s00453-011-9518-1openalex-snapshot
Graph Decomposition for Memoryless Periodic Exploration
inferred← citeshttps://doi.org/10.1016/0020-0255(82)90054-8openalex-snapshot
Pebble machines and tree walking machines
inferred← citeshttps://doi.org/10.1016/0022-0000(92)90046-lopenalex-snapshot
Lower bounds on the length of universal traversal sequences
inferred← citeshttps://doi.org/10.1016/0166-218x(90)90125-vopenalex-snapshot
Universal sequences for complete graphs
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00034-topenalex-snapshot
Reachability and the power of local ordering
inferred← citeshttps://doi.org/10.1016/0890-5401(90)90005-3openalex-snapshot
Milking the Aanderaa argument
inferred← citeshttps://doi.org/10.1016/j.disc.2015.01.018openalex-snapshot
Length lower bounds for reflecting sequences and universal traversal sequences
inferred← citeshttps://doi.org/10.1016/j.entcs.2011.09.025openalex-snapshot
Ramified Corecurrence and Logspace
inferred← citeshttps://doi.org/10.1016/j.ic.2018.05.006openalex-snapshot
A type-based complexity analysis of Object Oriented programs
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.09.004openalex-snapshot
Fast periodic graph exploration with constant memory
inferred← citeshttps://doi.org/10.1016/j.jcss.2017.06.006openalex-snapshot
Biconnectivity, st-numbering and other applications of DFS using O(n) bits
inferred← citeshttps://doi.org/10.1016/j.jcss.2021.07.004openalex-snapshot
Frameworks for designing in-place graph algorithms
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.09.040openalex-snapshot
Finite graph automata for linear and boundary graph languages
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.02.004openalex-snapshot
Distributed chasing of network intruders
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.03.035openalex-snapshot
Setting port numbers for fast graph exploration
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.01.035openalex-snapshot
More efficient periodic traversal in anonymous undirected graphs
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00019-0openalex-snapshot
A space lower bound for st-connectivity on node-named JAGs
inferred← citeshttps://doi.org/10.1016/s0895-7177(98)00156-3openalex-snapshot
Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
inferred← citeshttps://doi.org/10.1108/03684920210428218openalex-snapshot
Reaction‐diffusion and ant‐based load balancing of communication networks
inferred← citeshttps://doi.org/10.1109/ccc.2013.35openalex-snapshot
An O(n½+?)-Space and Polynomial-Time Algorithm for Directed Planar Reachability
inferred← citeshttps://doi.org/10.1109/focs.2010.58openalex-snapshot
Bounds on Monotone Switching Networks for Directed Connectivity
inferred← citeshttps://doi.org/10.1109/fscs.1990.89563openalex-snapshot
Time-space tradeoffs for undirected graph traversal
inferred← citeshttps://doi.org/10.1109/fscs.1990.89564openalex-snapshot
Constructing generalized universal traversing sequences of polynomial size for graphs with small diameter
inferred← citeshttps://doi.org/10.1109/lics.1995.523268openalex-snapshot
Tree canonization and transitive closure
inferred← citeshttps://doi.org/10.1109/lics.2009.41openalex-snapshot
Pointer Programs and Undirected Reachability
inferred← citeshttps://doi.org/10.1109/sct.1992.215378openalex-snapshot
A sublinear space, polynomial time algorithm for directed s-t connectivity
inferred← citeshttps://doi.org/10.1109/sct.1995.514723openalex-snapshot
Counting quantifiers, successor relations, and logarithmic space
inferred← citeshttps://doi.org/10.1109/sfcs.1983.31openalex-snapshot
Lower bounds on graph threading by probabilistic machines
inferred← citeshttps://doi.org/10.1109/sfcs.1988.21952openalex-snapshot
Reachability is harder for directed than for undirected finite graphs
inferred← citeshttps://doi.org/10.1109/sfcs.1992.267822openalex-snapshot
Undirected connectivity in O(log/sup 1.5/n) space
inferred← citeshttps://doi.org/10.1109/sfcs.1993.366864openalex-snapshot
Time-space lower bounds for directed s-t connectivity on JAG models
inferred← citeshttps://doi.org/10.1109/sfcs.1993.366865openalex-snapshot
Space bounds for graph connectivity problems on node-named JAGs and node-ordered JAGs
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365703openalex-snapshot
The power of team exploration: two robots can learn unlabeled directed graphs
inferred← citeshttps://doi.org/10.1137/0211050openalex-snapshot
On Some Deterministic Space Complexity Problems
inferred← citeshttps://doi.org/10.1137/s0097539790190144openalex-snapshot
Trading Space for Time in Undirected s - t Connectivity
inferred← citeshttps://doi.org/10.1137/s0097539793282947openalex-snapshot
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
inferred← citeshttps://doi.org/10.1137/s0097539793283151openalex-snapshot
A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
inferred← citeshttps://doi.org/10.1137/s0097539794277135openalex-snapshot
Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata
inferred← citeshttps://doi.org/10.1137/s0097539795294402openalex-snapshot
Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models
inferred← citeshttps://doi.org/10.1137/s0097539795295948openalex-snapshot
Tight Lower Bounds for st -Connectivity on the NNJAG Model
inferred← citeshttps://doi.org/10.1137/s009753979732428xopenalex-snapshot
Exploring Unknown Environments
inferred← citeshttps://doi.org/10.1142/s0219265919500087openalex-snapshot
Traversal with Enumeration of Geometric Graphs in Bounded Space
inferred← citeshttps://doi.org/10.1145/103418.103430openalex-snapshot
Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space.
inferred← citeshttps://doi.org/10.1145/167088.167272openalex-snapshot
Time-space trade-offs for undirected st -connectivity on a JAG
inferred← citeshttps://doi.org/10.1145/1805950.1805956openalex-snapshot
Pure pointer programs with iteration
inferred← citeshttps://doi.org/10.1145/225058.225103openalex-snapshot
A nearly optimal time-space lower bound for directed st -connectivity on the NNJAG model
inferred← citeshttps://doi.org/10.1145/237814.237882openalex-snapshot
Towards an analysis of local optimization algorithms
inferred← citeshttps://doi.org/10.1145/2438645.2438649openalex-snapshot
Delays Induce an Exponential Memory Gap for Rendezvous in Trees
inferred← citeshttps://doi.org/10.1145/3356883openalex-snapshot
Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
inferred← citeshttps://doi.org/10.1145/3717823.3718303openalex-snapshot
When Connectivity Is Hard, Random Walks Are Easy with Non-determinism
inferred← citeshttps://doi.org/10.1145/62212.62260openalex-snapshot
Polynomial universal traversing sequences for cycles are constructible
inferred← citeshttps://doi.org/10.1145/73007.73059openalex-snapshot
Trading space for time in undirected s-t connectivity
inferred← citeshttps://doi.org/10.1145/73007.73061openalex-snapshot
Lower bounds on the length of universal traversal sequences
inferred← citeshttps://doi.org/10.1145/800141.804679openalex-snapshot
On some deterministic space complexity problems
inferred← citeshttps://doi.org/10.2168/lmcs-3(2:3)2007openalex-snapshot
Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
inferred← citeshttps://doi.org/10.22215/etd/2021-14519openalex-snapshot
Search and Rendezvous by Mobile Robots in Continuous Domains
inferred← citeshttps://doi.org/10.2307/2274958openalex-snapshot
Reachability is harder for directed than for undirected finite graphs
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2008.1758openalex-snapshot
STCON in Directed Unique-Path Graphs
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2014.585openalex-snapshot
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2019.137openalex-snapshot
Energy Consumption of Group Search on a Line
inferred← citeshttps://doi.org/10.48550/arxiv.1310.8317openalex-snapshot
Power of Nondetreministic JAGs on Cayley graphs
inferred← citeshttps://doi.org/10.5555/2627817.2627950openalex-snapshot
Faster walks in graphs: a Õ(n2) time-space trade-off for undirected s-t connectivity
inferred← citeshttps://doi.org/10.70675/58e2747az6a79z40dezb604zbcda2fb26d19openalex-snapshot
Algorithms for deterministic parallel graph exploration
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.