On the public citation graph
Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
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/978-1-4613-9595-9openalex-snapshot
An Introduction to Formal Language Theory
inferredcites →https://doi.org/10.1007/bf00264016openalex-snapshot
Lower bounds on space complexity for contextfree recognition
inferredcites →https://doi.org/10.1007/bf00289080openalex-snapshot
A note on multihead automata and context-sensitive languages
inferredcites →https://doi.org/10.1007/bf01699458openalex-snapshot
On efficient deterministic simulation of turing machine computations below logaspace
inferredcites →https://doi.org/10.1007/bfb0028785openalex-snapshot
Space complexity of alternating Turing machines
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/0020-0190(87)90111-6openalex-snapshot
There are no fully space constructible functions between log log n and log n
inferredcites →https://doi.org/10.1016/0096-0551(80)90011-9openalex-snapshot
Introduction to automata theory, languages, and computation
inferredcites →https://doi.org/10.1016/0096-0551(80)90068-5openalex-snapshot
Introduction to formal language theory
inferredcites →https://doi.org/10.1016/0304-3975(76)90024-4openalex-snapshot
On tape bounds for single letter alphabet language processing
inferredcites →https://doi.org/10.1016/0304-3975(76)90072-4openalex-snapshot
Remarks on the complexity of nondeterministic counter languages
inferredcites →https://doi.org/10.1016/0304-3975(80)90053-5openalex-snapshot
Halting space-bounded computations
inferredcites →https://doi.org/10.1016/0378-4754(81)90068-9openalex-snapshot
Introduction to automata theory, languages and computation
inferredcites →https://doi.org/10.1016/s0019-9958(82)90382-5openalex-snapshot
Circuit-size lower bounds and non-reducibility to sparse sets
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(75)80052-3openalex-snapshot
Space bounds for processing contentless inputs
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/focs.1965.11openalex-snapshot
Hierarchies of memory limited computations
inferredcites →https://doi.org/10.1109/sfcs.1986.37openalex-snapshot
On the power one-way communication
inferredcites →https://doi.org/10.1145/44483.44493openalex-snapshot
On the power of one-way communication
inferredcites →https://doi.org/10.1145/800133.804357openalex-snapshot
Nondeterminism and the size of two way finite automata
inferredcites →https://doi.org/10.1145/990502.990506openalex-snapshot
A language over a one symbol alphabet requiring only O (log log n) space
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/jcss.1996.0046openalex-snapshot
Automaticity I: Properties of a Measure of Descriptional Complexity
inferred← citeshttps://doi.org/10.1007/11779148_40openalex-snapshot
On Some Variations of Two-Way Probabilistic Finite Automata Models
inferred← citeshttps://doi.org/10.1007/3-540-56287-7_121openalex-snapshot
Some observations on 2-way probabilistic finite automata
inferred← citeshttps://doi.org/10.1007/3-540-57785-8_176openalex-snapshot
Automaticity: Properties of a measure of descriptional complexity
inferred← citeshttps://doi.org/10.1007/978-3-030-81508-0_13openalex-snapshot
Two-Way Non-uniform Finite Automata
inferred← citeshttps://doi.org/10.1007/978-3-319-98355-4_1openalex-snapshot
Determinism and Nondeterminism in Finite Automata with Advice
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/bf01201276openalex-snapshot
Two-Way Automata and Length-Preserving Homomorphisms
inferred← citeshttps://doi.org/10.1007/s00224-013-9465-0openalex-snapshot
Two-Way Automata Versus Logarithmic Space
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90151-5openalex-snapshot
A survey of space complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.01.017openalex-snapshot
On some variations of two-way probabilistic finite automata models
inferred← citeshttps://doi.org/10.1137/0218083openalex-snapshot
Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
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/s0129054122440063openalex-snapshot
Two-Way Non-Uniform Finite Automata
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2021.39openalex-snapshot
Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines
inferred← citeshttps://doi.org/10.7146/dpb.v21i380.6612openalex-snapshot
On-Line Reevaluation of Functions
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.