On the public citation graph
The alternation hierarchy for sublogarithmic space is infinite
0 signed · 42 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.1007/3-540-56503-5_4openalex-snapshot
Separating the lower levels of the sublogarithmic space hierarchy
inferredcites →https://doi.org/10.1007/bf00299636openalex-snapshot
The method of forced enumeration for nondeterministic automata
inferredcites →https://doi.org/10.1007/bfb0032026openalex-snapshot
Nondeterministic computations in sublogarithmic space and space constructibility
inferredcites →https://doi.org/10.1007/bfb0035835openalex-snapshot
Collapsing oracle hierarchies, census functions and logarithmically many queries
inferredcites →https://doi.org/10.1016/0020-0190(87)90085-8openalex-snapshot
Some observations concerning alternating turing machines using small space
inferredcites →https://doi.org/10.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/0025-5564(87)90102-7openalex-snapshot
Computational complexity
inferredcites →https://doi.org/10.1016/0304-3975(80)90053-5openalex-snapshot
Halting space-bounded computations
inferredcites →https://doi.org/10.1016/0304-3975(87)90138-1openalex-snapshot
On reversal bounded alternating Turing machines
inferredcites →https://doi.org/10.1016/b978-0-444-88071-0.50006-0openalex-snapshot
Machine Models and Simulations
inferredcites →https://doi.org/10.1016/s0049-237x(08)x7014-4openalex-snapshot
Computability, Complexity, Logic
inferredcites →https://doi.org/10.1109/focs.1965.14openalex-snapshot
Memory bounds for recognition of context-free and context-sensitive languages
inferredcites →https://doi.org/10.1137/0217058openalex-snapshot
Nondeterministic Space is Closed under Complementation
inferredcites →https://doi.org/10.1137/0219014openalex-snapshot
Reversal Complexity Classes for Alternating Turing Machines
inferredcites →https://doi.org/10.1137/0222009openalex-snapshot
Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
inferredcites →https://doi.org/10.1137/0222011openalex-snapshot
${\text{ASPACE}}(o(\log \log n))$ is Regular
inferredcites →https://doi.org/10.1145/28395.28408openalex-snapshot
The strong exponential hierarchy collapses
inferredcites →https://doi.org/10.1145/800061.808733openalex-snapshot
Borel sets and circuit complexity
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.0084openalex-snapshot
Inductive Counting for Width-Restricted Branching Programs
inferred← citeshttps://doi.org/10.1006/inco.1997.2682openalex-snapshot
Bridging across the log(n) Space Frontier
inferred← citeshttps://doi.org/10.1007/3-540-44683-4_34openalex-snapshot
Space Hierarchy Theorem Revised
inferred← citeshttps://doi.org/10.1007/3-540-57785-8_133openalex-snapshot
The alternation hierarchy for machines with sublogarithmic space is infinite
inferred← citeshttps://doi.org/10.1007/3-540-58338-6_74openalex-snapshot
Inductive counting below logspace
inferred← citeshttps://doi.org/10.1007/978-3-540-24587-2_65openalex-snapshot
Some Properties of One-Pebble Turing Machines with Sublogarithmic Space
inferred← citeshttps://doi.org/10.1007/978-3-662-53132-7_16openalex-snapshot
Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space
inferred← citeshttps://doi.org/10.1007/bfb0029952openalex-snapshot
Computational limitations of Stochastic Turing machines and Arthur-Merlin games with small space bounds
inferred← citeshttps://doi.org/10.1016/j.ic.2017.02.001openalex-snapshot
Alternating space is closed under complement and other simulations for sublogarithmic space
inferred← citeshttps://doi.org/10.1016/j.ins.2003.09.012openalex-snapshot
A note on one-pebble two-dimensional Turing machines
inferred← citeshttps://doi.org/10.1016/j.ipl.2007.11.005openalex-snapshot
Fooling Turing machines with sublogarithmic space: a note on ‘For completeness, sublogarithmic space is no space’ by M. Agrawal
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.04.003openalex-snapshot
Some properties of one-pebble Turing machines with sublogarithmic space
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.04.044openalex-snapshot
An alternating hierarchy for finite automata
inferred← citeshttps://doi.org/10.1016/s0020-0190(01)00296-4openalex-snapshot
For completeness, sublogarithmic space is no space
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00035-9openalex-snapshot
Alternation for sublogarithmic space-bounded alternating pushdown automata
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00402-4openalex-snapshot
Space hierarchy theorem revised
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00338-2openalex-snapshot
A variant of inductive counting
inferred← citeshttps://doi.org/10.1016/s1571-0653(04)00499-8openalex-snapshot
A note on one-pebble two-dimensional Turing machines
inferred← citeshttps://doi.org/10.1142/s0129054101000552openalex-snapshot
CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES
inferred← citeshttps://doi.org/10.1142/s012905410800598xopenalex-snapshot
TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
inferred← citeshttps://doi.org/10.1587/transfun.2019dml0001openalex-snapshot
Non-Closure Properties of Multi-Inkdot Nondeterministic Turing Machines with Sublogarithmic Space
inferred← citeshttps://doi.org/10.1587/transfun.e93.a.1148openalex-snapshot
Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
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.