On the public citation graph
Space complexity of alternating Turing machines
0 signed · 37 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-09510-1_34openalex-snapshot
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
inferredcites →https://doi.org/10.1016/0020-0190(82)90098-9openalex-snapshot
A note on alternating on-line Turing machines
inferredcites →https://doi.org/10.1016/0304-3975(82)90075-5openalex-snapshot
On eliminating nondeterminism from turing machines which use less than logarithm worktape space
inferredcites →https://doi.org/10.1109/focs.1965.11openalex-snapshot
Hierarchies of memory limited computations
inferredcites →https://doi.org/10.1109/sfcs.1980.17openalex-snapshot
Efficient algorithms for path system problems and applications to alternating and time-space complexity classes
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.1997.2682openalex-snapshot
Bridging across the log(n) Space Frontier
inferred← citeshttps://doi.org/10.1006/jcss.2002.1855openalex-snapshot
Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds
inferred← citeshttps://doi.org/10.1007/3-540-44612-5_55openalex-snapshot
Unary Pushdown Automata and Auxiliary Space Lower Bounds
inferred← citeshttps://doi.org/10.1007/3-540-60246-1_112openalex-snapshot
Bridging across the log(n) space frontier
inferred← citeshttps://doi.org/10.1007/3-540-60246-1_137openalex-snapshot
Strong optimal lower bounds for Turing machines that accept nonregular languages
inferred← citeshttps://doi.org/10.1007/978-3-030-23247-4_20openalex-snapshot
Pushdown Automata and Constant Height: Decidability and Bounds
inferred← citeshttps://doi.org/10.1007/978-3-031-34326-1_11openalex-snapshot
Pushdown and One-Counter Automata: Constant and Non-constant Memory Usage
inferred← citeshttps://doi.org/10.1007/978-3-031-71112-1_21openalex-snapshot
Push Complexity: Optimal Bounds and Unary Inputs
inferred← citeshttps://doi.org/10.1007/978-3-319-30000-9_3openalex-snapshot
Restricted Turing Machines and Language Recognition
inferred← citeshttps://doi.org/10.1007/978-3-319-92402-1_6openalex-snapshot
Minimal Useful Size of Counters for (Real-Time) Multicounter Automata
inferred← citeshttps://doi.org/10.1007/978-3-642-20712-9_28openalex-snapshot
Two-Way Automata versus Logarithmic Space
inferred← citeshttps://doi.org/10.1007/bf02088003openalex-snapshot
Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
inferred← citeshttps://doi.org/10.1007/s00224-013-9465-0openalex-snapshot
Two-Way Automata Versus Logarithmic Space
inferred← citeshttps://doi.org/10.1007/s00236-022-00434-0openalex-snapshot
Pushdown automata and constant height: decidability and bounds
inferred← citeshttps://doi.org/10.1016/0020-0190(87)90085-8openalex-snapshot
Some observations concerning alternating turing machines using small space
inferred← citeshttps://doi.org/10.1016/0020-0190(88)90026-9openalex-snapshot
Remarks on languages acceptable in log log n space
inferred← citeshttps://doi.org/10.1016/0020-0190(89)90158-0openalex-snapshot
Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
inferred← citeshttps://doi.org/10.1016/0020-0190(89)90163-4openalex-snapshot
Some notes on strong and weak log log n space complexity
inferred← citeshttps://doi.org/10.1016/0020-0190(95)00151-2openalex-snapshot
A remark on middle space bounded alternating Turing machines
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90151-5openalex-snapshot
A survey of space complexity
inferred← citeshttps://doi.org/10.1016/s0020-0190(98)00176-8openalex-snapshot
Weak and strong one-way space complexity classes
inferred← citeshttps://doi.org/10.1051/ita:2000101openalex-snapshot
A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines
inferred← citeshttps://doi.org/10.1137/0219014openalex-snapshot
Reversal Complexity Classes for Alternating Turing Machines
inferred← citeshttps://doi.org/10.1137/0222011openalex-snapshot
${\text{ASPACE}}(o(\log \log n))$ is Regular
inferred← citeshttps://doi.org/10.1137/s0097539796301306openalex-snapshot
Sublogarithmic Bounds on Space and Reversals
inferred← citeshttps://doi.org/10.1145/1998476.1998480openalex-snapshot
Passively mobile communicating machines that use restricted space
inferred← citeshttps://doi.org/10.2200/s00328ed1v01y201101dct006openalex-snapshot
New Models for Population Protocols
inferred← citeshttps://doi.org/10.25596/jalc-2009-107openalex-snapshot
Nondeterministic One-Tape Off-Line Turing Machines and Their Time Complexity
inferred← citeshttps://doi.org/10.48550/arxiv.1507.08582openalex-snapshot
One-Tape Turing Machine Variants and Language Recognition
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.