On the public citation graph
The expressive power of second order Horn logic
0 signed · 45 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-18170-9_158openalex-snapshot
Skolem normal forms concerning the least fixpoint
inferredcites →https://doi.org/10.1007/3-540-51498-8_23openalex-snapshot
Descriptive and computational complexity
inferredcites →https://doi.org/10.1007/bf00289267openalex-snapshot
The equivalence of Horn and network complexity for Boolean functions
inferredcites →https://doi.org/10.1016/0022-0000(82)90012-5openalex-snapshot
Structure and complexity of relational queries
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(76)90068-2openalex-snapshot
Complete problems for deterministic polynomial time
inferredcites →https://doi.org/10.1016/0743-1066(84)90014-1openalex-snapshot
Linear-time algorithms for testing the satisfiability of propositional horn formulae
inferredcites →https://doi.org/10.1016/0743-1066(85)90002-0openalex-snapshot
Horn clause queries and generalizations
inferredcites →https://doi.org/10.1016/0743-1066(87)90014-8openalex-snapshot
Unification as a complexity measure for logic programming
inferredcites →https://doi.org/10.1016/0890-5401(91)90059-bopenalex-snapshot
The expressive power of stratified logic programs
inferredcites →https://doi.org/10.1016/s0019-9958(86)80029-8openalex-snapshot
Relational queries computable in polynomial time
inferredcites →https://doi.org/10.1090/psapm/038/1020810openalex-snapshot
Descriptive and computational complexity
inferredcites →https://doi.org/10.1109/psct.1987.10319271openalex-snapshot
Expressibility as a Complexity Measure: Results and Directions
inferredcites →https://doi.org/10.1137/0216051openalex-snapshot
Languages that Capture Complexity Classes
inferredcites →https://doi.org/10.1145/800070.802186openalex-snapshot
The complexity of relational query languages (Extended Abstract)
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/malq.201110034openalex-snapshot
Complexity and expressive power of second‐order extended Horn logic
inferred← citeshttps://doi.org/10.1007/11538363_26openalex-snapshot
Closure Properties of Weak Systems of Bounded Arithmetic
inferred← citeshttps://doi.org/10.1007/3-540-48242-3_13openalex-snapshot
On the Complexity of Single-Rule Datalog Queries
inferred← citeshttps://doi.org/10.1007/978-3-030-19570-0_17openalex-snapshot
SLD-Resolution Reduction of Second-Order Horn Fragments
inferred← citeshttps://doi.org/10.1007/978-3-031-45558-2_9openalex-snapshot
The Expressive Power of Revised Datalog on Problems with Closure Properties
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-3-319-43669-2_10openalex-snapshot
Complexity Barriers as Independence
inferred← citeshttps://doi.org/10.1007/978-3-540-69407-6_35openalex-snapshot
Many Facets of Complexity in Logic
inferred← citeshttps://doi.org/10.1007/978-3-642-60322-8_8openalex-snapshot
Spectral Problems and Descriptive Complexity Theory
inferred← citeshttps://doi.org/10.1007/bfb0023481openalex-snapshot
Algebraic and logical characterizations of deterministic linear time classes
inferred← citeshttps://doi.org/10.1016/s0168-0072(03)00056-3openalex-snapshot
A second-order system for polytime reasoning based on Grädel's theorem
inferred← citeshttps://doi.org/10.1016/s0890-5401(03)00012-9openalex-snapshot
On the complexity of single-rule datalog queries
inferred← citeshttps://doi.org/10.1080/02331934.2011.625027openalex-snapshot
Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
inferred← citeshttps://doi.org/10.1093/logcom/exq008openalex-snapshot
Expressing versus Proving: Relating Forms of Complexity in Logic
inferred← citeshttps://doi.org/10.1109/lics.1998.705640openalex-snapshot
Existential second-order logic over strings
inferred← citeshttps://doi.org/10.1109/lics.2001.932495openalex-snapshot
A second-order system for polytime reasoning using Gradel's theorem
inferred← citeshttps://doi.org/10.1109/sct.1991.160279openalex-snapshot
Capturing complexity classes by fragments of second order logic
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892334openalex-snapshot
Existential second-order logic over graphs: charting the tractability frontier
inferred← citeshttps://doi.org/10.1145/331605.331609openalex-snapshot
Existential second-order logic over strings
inferred← citeshttps://doi.org/10.1145/3779416openalex-snapshot
An Abstract Fixed-Point Theorem for Horn Formula Equations
inferred← citeshttps://doi.org/10.1145/972639.972646openalex-snapshot
Existential second-order logic over graphs
inferred← citeshttps://doi.org/10.4204/eptcs.344.5openalex-snapshot
A Fixed-point Theorem for Horn Formula Equations
inferred← citeshttps://doi.org/10.46298/lmcs-19(3:6)2023openalex-snapshot
Capturing the polynomial hierarchy by second-order revised Krom logic
inferred← citeshttps://doi.org/10.48550/arxiv.0909.5521openalex-snapshot
Clique and Vertex Cover are solvable in polynomial time if the input structure is ordered and contains a successor predicate
inferred← citeshttps://doi.org/10.48550/arxiv.1004.1814openalex-snapshot
Existential Second Order Logic Expression With Horn First Order for Maximum Clique (Decision Version)
inferred← citeshttps://doi.org/10.48550/arxiv.1106.4606openalex-snapshot
Expressibility at the machine level versus structure level: ESO universal Horn Logic and the class P
inferred← citeshttps://doi.org/10.48550/arxiv.1902.09900openalex-snapshot
SLD-Resolution Reduction of Second-Order Horn Fragments -- technical report --
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0606050openalex-snapshot
Syntactic Characterisations of Polynomial-Time Optimisation Classes (Syntactic Characterizations of Polynomial-Time Optimization Classes)
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.