On the public citation graph

On Existentially First-Order Definable Languages and Their Relation to NP

https://doi.org/10.1007/bfb0055037
0 signed · 35 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.1006/jcss.1995.1028openalex-snapshot
On Unique Satisfiability and the Threshold Behavior of Randomized Reductions
inferredcites →https://doi.org/10.1007/978-1-4612-0289-9openalex-snapshot
Finite Automata, Formal Logic, and Circuit Complexity
inferredcites →https://doi.org/10.1007/bf02679467openalex-snapshot
Polynomial closure and unambiguous product
inferredcites →https://doi.org/10.1007/s002240000058openalex-snapshot
Polynomial Closure and Unambiguous Product
inferredcites →https://doi.org/10.1016/0022-0000(82)90016-2openalex-snapshot
Classifying regular events in symbolic logic
inferredcites →https://doi.org/10.1016/0022-0000(86)90037-1openalex-snapshot
First-order logic and star-free sets
inferredcites →https://doi.org/10.1016/0304-3975(92)90084-sopenalex-snapshot
Counting classes: thresholds, parity, mods, and fewness
inferredcites →https://doi.org/10.1016/0304-3975(92)90125-yopenalex-snapshot
A uniform approach to define complexity classes
inferredcites →https://doi.org/10.1016/0304-3975(95)00032-ropenalex-snapshot
On the acceptance power of regular languages
inferredcites →https://doi.org/10.1016/s0019-9958(82)90439-9openalex-snapshot
On the unique satisfiability problem
inferredcites →https://doi.org/10.1109/sct.1993.336526openalex-snapshot
On the power of polynomial time bit-reductions
inferredcites →https://doi.org/10.1137/0217078openalex-snapshot
The Boolean Hierarchy I: Structural Properties
inferredcites →https://doi.org/10.1137/0220053openalex-snapshot
PP is as Hard as the Polynomial-Time Hierarchy
inferredcites →https://doi.org/10.1142/s0129054198000180openalex-snapshot
LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY

What points at this work

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

inferred← citeshttps://doi.org/10.1007/11494645_53openalex-snapshot
Some Reducibilities on Regular Sets
inferred← citeshttps://doi.org/10.1007/11549345_34openalex-snapshot
Autoreducibility, Mitoticity, and Immunity
inferred← citeshttps://doi.org/10.1007/11779148_37openalex-snapshot
Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
inferred← citeshttps://doi.org/10.1007/11821069_38openalex-snapshot
Machines that Can Output Empty Words
inferred← citeshttps://doi.org/10.1007/3-540-44669-9_31openalex-snapshot
Relating Automata-Theoretic Hierarchies to Complexity-Theoretic Hierarchies
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/978-3-540-28629-5_61openalex-snapshot
A Reducibility for the Dot-Depth Hierarchy
inferred← citeshttps://doi.org/10.1007/978-3-540-30550-7_8openalex-snapshot
The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels
inferred← citeshttps://doi.org/10.1007/978-3-540-31834-7_5openalex-snapshot
Leaf Language Classes
inferred← citeshttps://doi.org/10.1007/978-3-540-31856-9_14openalex-snapshot
Polylog-Time Reductions Decrease Dot-Depth
inferred← citeshttps://doi.org/10.1007/bfb0055073openalex-snapshot
Bridges for concatenation hierarchies
inferred← citeshttps://doi.org/10.1016/j.jcss.2006.09.004openalex-snapshot
Languages polylog-time reducible to dot-depth 1/2
inferred← citeshttps://doi.org/10.1016/j.jcss.2006.10.020openalex-snapshot
Autoreducibility, mitoticity, and immunity
inferred← citeshttps://doi.org/10.1016/j.jcss.2014.03.006openalex-snapshot
Perfect correspondences between dot-depth and polynomial-time hierarchies
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.07.020openalex-snapshot
A reducibility for the dot-depth hierarchy
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.06.031openalex-snapshot
Fine hierarchies and m-reducibilities in theoretical computer science
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00230-4openalex-snapshot
Algebraic tools for the concatenation product
inferred← citeshttps://doi.org/10.1051/ita:2002003openalex-snapshot
Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
inferred← citeshttps://doi.org/10.1051/ita:2007063openalex-snapshot
Hierarchies and reducibilities on regular languages related to modulo counting
inferred← citeshttps://doi.org/10.1142/s0129054105003200openalex-snapshot
THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9809118openalex-snapshot
The Boolean Hierarchy over Level 1/2 of the Straubing-Therien Hierarchy
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.