On the public citation graph

Invariance properties of RAMS and linear time

https://doi.org/10.1007/bf01205055
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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-51237-3_10openalex-snapshot
Nearly linear time
inferredcites →https://doi.org/10.1007/978-3-642-69965-8_23openalex-snapshot
Computational Complexity
inferredcites →https://doi.org/10.1007/bf01699468openalex-snapshot
Universal quantifiers and time complexity of random access machines
inferredcites →https://doi.org/10.1016/0020-0190(89)90117-8openalex-snapshot
Space measures for storage modification machines
inferredcites →https://doi.org/10.1016/0020-0190(90)90133-iopenalex-snapshot
Random access machines with multi-dimensional memories
inferredcites →https://doi.org/10.1016/0022-0000(79)90045-xopenalex-snapshot
Fast probabilistic algorithms for hamiltonian circuits and matchings
inferredcites →https://doi.org/10.1016/0022-0000(90)90009-aopenalex-snapshot
First-order spectra with one variable
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/0304-3975(92)90149-aopenalex-snapshot
Capturing complexity classes by fragments of second-order logic
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/0890-5401(88)90052-1openalex-snapshot
The problem of space invariance for sequential 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/s0019-9958(86)80029-8openalex-snapshot
Relational queries computable in polynomial time
inferredcites →https://doi.org/10.1016/s0022-0000(73)80029-7openalex-snapshot
Time bounded random access machines
inferredcites →https://doi.org/10.1109/sct.1991.160279openalex-snapshot
Capturing complexity classes by fragments of second order logic
inferredcites →https://doi.org/10.1109/sfcs.1975.23openalex-snapshot
On time versus space and related problems
inferredcites →https://doi.org/10.1137/0209036openalex-snapshot
Storage Modification Machines
inferredcites →https://doi.org/10.1137/0217005openalex-snapshot
Fast Simulation of Turing Machines by Random Access Machines
inferredcites →https://doi.org/10.1137/s0097539791223206openalex-snapshot
Linear Time Algorithms and NP-Complete Problems
inferredcites →https://doi.org/10.1145/321724.321726openalex-snapshot
Real-Time Simulation of Multihead Tape Units
inferredcites →https://doi.org/10.1145/322003.322015openalex-snapshot
On Time Versus Space
inferredcites →https://doi.org/10.1145/322047.322060openalex-snapshot
Satisfiability Is Quasilinear Complete in NQL
inferredcites →https://doi.org/10.1145/44483.44492openalex-snapshot
A nonlinear lower bound for random-access machines under logarithmic cost

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.2002.3027openalex-snapshot
Linear Time and the Power of One First-Order Universal Quantifier
inferred← citeshttps://doi.org/10.1007/10703163_2openalex-snapshot
Descriptive Complexity, Lower Bounds and Linear Time
inferred← citeshttps://doi.org/10.1007/3-540-48168-0_23openalex-snapshot
MonadicNLIN and Quantifier-Free Reductions
inferred← citeshttps://doi.org/10.1007/3-540-49116-3_13openalex-snapshot
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines
inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_93openalex-snapshot
On the Expressive Power of Monadic Least Fixed Point Logic
inferred← citeshttps://doi.org/10.1007/bf02127798openalex-snapshot
Sorting, linear time and the satisfiability problem
inferred← citeshttps://doi.org/10.1007/bfb0023481openalex-snapshot
Algebraic and logical characterizations of deterministic linear time classes
inferred← citeshttps://doi.org/10.1007/pl00001594openalex-snapshot
Monadic logical definability of nondeterministic linear time
inferred← citeshttps://doi.org/10.1016/j.jcss.2003.09.002openalex-snapshot
Graph properties checkable in linear time in the number of vertices
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.025openalex-snapshot
On the expressive power of monadic least fixed point logic
inferred← citeshttps://doi.org/10.1109/sct.1995.514727openalex-snapshot
On superlinear lower bounds in complexity theory
inferred← citeshttps://doi.org/10.1137/s0097539791223206openalex-snapshot
Linear Time Algorithms and NP-Complete Problems
inferred← citeshttps://doi.org/10.1137/s0097539799360240openalex-snapshot
Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
inferred← citeshttps://doi.org/10.1142/s0129054108005632openalex-snapshot
A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES
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.