On the public citation graph

Oracles and quantifiers

https://doi.org/10.1007/bfb0049333
0 signed · 55 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-13331-3_51openalex-snapshot
Reduction to NP-complete problems by interpretations
inferredcites →https://doi.org/10.1007/3-540-16486-3_111openalex-snapshot
Parallel computation and the NC hierarchy relativized
inferredcites →https://doi.org/10.1007/3-540-55251-0_7openalex-snapshot
Monadic second-order definable graph transductions
inferredcites →https://doi.org/10.1007/bf01683260openalex-snapshot
Relativization of questions about log space computability
inferredcites →https://doi.org/10.1016/0022-0000(80)90032-xopenalex-snapshot
Computable queries for relational data bases
inferredcites →https://doi.org/10.1016/0022-0000(82)90012-5openalex-snapshot
Structure and complexity of relational queries
inferredcites →https://doi.org/10.1016/0022-0000(84)90066-7openalex-snapshot
Space-bounded hierarchies and probabilistic computations
inferredcites →https://doi.org/10.1016/0022-0000(88)90034-7openalex-snapshot
Relativized alternation and space-bounded computation
inferredcites →https://doi.org/10.1016/0022-0000(92)90043-iopenalex-snapshot
Using the Hamiltonian path operator to capture NP
inferredcites →https://doi.org/10.1016/0168-0072(89)90070-5openalex-snapshot
Definability hierarchies of generalized quantifiers
inferredcites →https://doi.org/10.1016/0168-0072(94)90036-1openalex-snapshot
Context-sensitive transitive closure operators
inferredcites →https://doi.org/10.1016/0304-3975(78)90003-8openalex-snapshot
Log space machines with multiple oracle tapes
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/b978-0-444-88071-0.50007-2openalex-snapshot
A Catalog of Complexity Classes
inferredcites →https://doi.org/10.1016/s0019-9958(86)80029-8openalex-snapshot
Relational queries computable in polynomial time
inferredcites →https://doi.org/10.1016/s0065-2458(08)60462-3openalex-snapshot
Information and Computation
inferredcites →https://doi.org/10.1093/logcom/1.3.305openalex-snapshot
Comparing the Expressibility of Languages Formed Using NP-Complete Operators
inferredcites →https://doi.org/10.1093/logcom/5.2.213openalex-snapshot
Generalized Quantifiers and Logical Reducibilities
inferredcites →https://doi.org/10.1109/lics.1992.185548openalex-snapshot
Logical hierarchies in PTIME
inferredcites →https://doi.org/10.1109/sct.1993.336519openalex-snapshot
Computing functions with parallel queries to NP
inferredcites →https://doi.org/10.1111/j.1755-2567.1966.tb00600.xopenalex-snapshot
First Order Predicate Logic with Generalized Quantifiers
inferredcites →https://doi.org/10.1111/j.1755-2567.1969.tb00356.xopenalex-snapshot
On Extensions of Elementary Logic
inferredcites →https://doi.org/10.1137/0216051openalex-snapshot
Languages that Capture Complexity Classes
inferredcites →https://doi.org/10.1137/0217058openalex-snapshot
Nondeterministic Space is Closed under Complementation
inferredcites →https://doi.org/10.1137/0218043openalex-snapshot
Expressibility and Parallel Complexity
inferredcites →https://doi.org/10.1137/0219058openalex-snapshot
Bounded Query Classes
inferredcites →https://doi.org/10.1145/321978.321989openalex-snapshot
A Combinatorial Problem Which Is Complete in Polynomial Space
inferredcites →https://doi.org/10.1145/322234.322243openalex-snapshot
Alternation
inferredcites →https://doi.org/10.1145/800070.802186openalex-snapshot
The complexity of relational query languages (Extended Abstract)
inferredcites →https://doi.org/10.1145/800070.802187openalex-snapshot
Relational queries computable in polynomial time (Extended Abstract)
inferredcites →https://doi.org/10.1145/800105.803405openalex-snapshot
Reducibility, randomness, and intractibility (Abstract)
inferredcites →https://doi.org/10.2307/2273858openalex-snapshot
Classifying the computational complexity of problems
inferredcites →https://doi.org/10.3233/fi-1993-18105openalex-snapshot
Logical Characterizations of Bounded Query Classes I: Logspace Oracle Machines
inferredcites →https://doi.org/10.3233/fi-1993-18106openalex-snapshot
Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machine

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/9781119357056.ch4openalex-snapshot
Incremental Verification and Coverage Analysis of Strongly Distributed Systems
inferred← citeshttps://doi.org/10.1002/malq.19970430203openalex-snapshot
Logics with Zero‐One Laws that Are Not Fragments of Bounded‐Variable Infinitary Logic
inferred← citeshttps://doi.org/10.1006/inco.1996.0070openalex-snapshot
Logical Hierarchies in PTIME
inferred← citeshttps://doi.org/10.1007/10703163_10openalex-snapshot
Invariant Definability and P/poly
inferred← citeshttps://doi.org/10.1007/3-540-46583-9_3openalex-snapshot
A Perspective on Lindström Quantifiers and Oracles
inferred← citeshttps://doi.org/10.1007/3-540-46583-9_4openalex-snapshot
Generalized Quantifiers in Logic Programs
inferred← citeshttps://doi.org/10.1007/3-540-46583-9_5openalex-snapshot
A Generalized Quantifier Concept in Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/3-540-58338-6_59openalex-snapshot
Capturing complexity classes with Lindström quantifiers
inferred← citeshttps://doi.org/10.1007/3-540-60178-3_98openalex-snapshot
Logics capturing relativized complexity classes uniformly
inferred← citeshttps://doi.org/10.1007/3-540-63385-5_43openalex-snapshot
Invariant definability
inferred← citeshttps://doi.org/10.1007/978-3-030-78163-7_18openalex-snapshot
A Logic-Based Approach to Incremental Reasoning on Multi-agent Systems
inferred← citeshttps://doi.org/10.1007/978-3-031-86319-6_14openalex-snapshot
NP-completeness by First-order and Quantifier-free Interpretations and Related Topics
inferred← citeshttps://doi.org/10.1007/978-3-319-23534-9_14openalex-snapshot
Logics of Finite Hankel Rank
inferred← citeshttps://doi.org/10.1007/978-94-017-3327-4_10openalex-snapshot
Capturing Relativized Complexity Classes with Lindström Quantifiers
inferred← citeshttps://doi.org/10.1007/bf01057805openalex-snapshot
Directions in generalized quantifier theory
inferred← citeshttps://doi.org/10.1016/s0020-0190(97)00116-6openalex-snapshot
Generalized Hex and logical characterizations of polynomial space
inferred← citeshttps://doi.org/10.1109/lics.1995.523245openalex-snapshot
Relativized logspace and generalized quantifiers over finite structures
inferred← citeshttps://doi.org/10.2307/2275546openalex-snapshot
Relativized logspace and generalized quantifiers over finite ordered structures
inferred← citeshttps://doi.org/10.2307/2275847openalex-snapshot
Complete problems for fixed-point logics
inferred← citeshttps://doi.org/10.29007/45rvopenalex-snapshot
A Uniform Approach to Incremental Automated Reasoning on Strongly Distributed Structures
inferred← citeshttps://doi.org/10.4230/lipics.csl.2011.553openalex-snapshot
Model Theory in Computer Science: My Own Recurrent Themes
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.