On the public citation graph

Polynomial-time inference of all valid implications for Horn and related formulae

https://doi.org/10.1007/bf01531068
0 signed · 104 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/bf01531084openalex-snapshot
Question-asking strategies for Horn clause systems
inferredcites →https://doi.org/10.1007/bf01580586openalex-snapshot
A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
inferredcites →https://doi.org/10.1007/bf02186368openalex-snapshot
Generalized resolution and cutting planes
inferredcites →https://doi.org/10.1016/0020-0190(76)90079-xopenalex-snapshot
A cascade algorithm for the logical closure of a set of binary relations
inferredcites →https://doi.org/10.1016/0020-0190(79)90002-4openalex-snapshot
A linear-time algorithm for testing the truth of certain quantified boolean formulas
inferredcites →https://doi.org/10.1016/0020-0190(88)90124-xopenalex-snapshot
LTUR: a simplified linear-time unit resolution algorithm for horn formulae and computer implementation
inferredcites →https://doi.org/10.1016/0167-9236(88)90097-8openalex-snapshot
A quantitative approach to logical inference
inferredcites →https://doi.org/10.1016/0196-6774(80)90007-3openalex-snapshot
Recognizing disguised NR(1) instances of the satisfiability problem
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(87)90014-8openalex-snapshot
Unification as a complexity measure for logic programming
inferredcites →https://doi.org/10.1016/c2009-0-22103-9openalex-snapshot
Symbolic Logic and Mechanical Theorem Proving
inferredcites →https://doi.org/10.1080/00029890.1955.11988710openalex-snapshot
A Way to Simplify Truth Functions
inferredcites →https://doi.org/10.1080/00029890.1959.11989404openalex-snapshot
On Cores and Prime Implicants of Truth Functions
inferredcites →https://doi.org/10.1109/tc.1968.229129openalex-snapshot
The Origin of the Method of Iterated Consensus
inferredcites →https://doi.org/10.1137/0208032openalex-snapshot
The Complexity of Enumeration and Reliability Problems
inferredcites →https://doi.org/10.1145/1005937.1005947openalex-snapshot
Logic for problem solving
inferredcites →https://doi.org/10.1145/321250.321253openalex-snapshot
A Machine-Oriented Logic Based on the Resolution Principle
inferredcites →https://doi.org/10.1145/322047.322059openalex-snapshot
Renaming a Set of Clauses as a Horn Set
inferredcites →https://doi.org/10.1145/800133.804350openalex-snapshot
The complexity of satisfiability problems
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.1515/zwf-1986-811227openalex-snapshot
Building Expert Systems
inferredcites →https://doi.org/10.2307/2267634openalex-snapshot
Archie Blake. Canonical expressions in Boolean algebra. Dissertation Chicago 1937. Lithographed. The University of Chicago Libraries, Chicago1938, ii + 60 pp.

What points at this work

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

inferred← citeshttps://doi.org/10.1002/9781118033166.biblioopenalex-snapshot
Bibliography
inferred← citeshttps://doi.org/10.1007/3-540-40006-0_22openalex-snapshot
New Tractable Cases in Default Reasoning from Conditional Knowledge Bases
inferred← citeshttps://doi.org/10.1007/3-540-44929-9_20openalex-snapshot
Fully Consistent Extensions of Partially Defined Boolean Functions with Missing Bitsv
inferred← citeshttps://doi.org/10.1007/3-540-45757-7_52openalex-snapshot
Z-log: Applying System-Z
inferred← citeshttps://doi.org/10.1007/3-540-60299-2_31openalex-snapshot
Polynomial restrictions of SAT: What can be done with an efficient implementation of the Davis and Putnam's procedure?
inferred← citeshttps://doi.org/10.1007/978-1-4419-6800-5_1openalex-snapshot
Complete and Exact Peptide Sequence Analysis Based on Propositional Logic
inferred← citeshttps://doi.org/10.1007/978-1-4419-7997-1_31openalex-snapshot
Algorithms for the Satisfiability Problem
inferred← citeshttps://doi.org/10.1007/978-1-4757-3023-4_7openalex-snapshot
Algorithms for the Satisfiability (SAT) Problem
inferred← citeshttps://doi.org/10.1007/978-3-319-40970-2_4openalex-snapshot
Strong Backdoors for Default Logic
inferred← citeshttps://doi.org/10.1007/978-3-319-99344-7_18openalex-snapshot
Tractable Classes in Exactly-One-SAT
inferred← citeshttps://doi.org/10.1007/978-3-540-39624-6_1openalex-snapshot
Abduction and the Dualization Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-39644-4_1openalex-snapshot
Abduction and the Dualization Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-45220-1_18openalex-snapshot
Generating All Abductive Explanations for Queries on Propositional Horn Theories
inferred← citeshttps://doi.org/10.1007/978-3-540-73099-6_16openalex-snapshot
A Bottom-Up Approach to Clausal Tableaux
inferred← citeshttps://doi.org/10.1007/978-3-540-76928-6_25openalex-snapshot
A CNF Formula Hierarchy over the Hypercube
inferred← citeshttps://doi.org/10.1007/978-3-540-79719-7_22openalex-snapshot
A CNF Class Generalizing Exact Linear Formulas
inferred← citeshttps://doi.org/10.1007/978-3-642-14165-2_38openalex-snapshot
On Approximate Horn Formula Minimization
inferred← citeshttps://doi.org/10.1007/978-94-017-1737-3_3openalex-snapshot
Consequence Finding Algorithms
inferred← citeshttps://doi.org/10.1007/bf02127974openalex-snapshot
Hierarchies of polynomially solvable satisfiability problems
inferred← citeshttps://doi.org/10.1007/s00453-014-9958-5openalex-snapshot
Backdoors to q-Horn
inferred← citeshttps://doi.org/10.1007/s10472-004-9418-zopenalex-snapshot
On Exact Selection of Minimally Unsatisfiable Subformulae
inferred← citeshttps://doi.org/10.1007/s10472-015-9452-zopenalex-snapshot
About some UP-based polynomial fragments of SAT
inferred← citeshttps://doi.org/10.1007/s10479-009-0637-xopenalex-snapshot
Incremental polynomial time dualization of quadratic functions and a subclass of degree-k functions
inferred← citeshttps://doi.org/10.1007/s10852-010-9136-yopenalex-snapshot
A Logic-Based Approach to Polymer Sequence Analysis
inferred← citeshttps://doi.org/10.1007/s12543-011-0083-8openalex-snapshot
Properties of Quasi-Boolean Function on Quasi-Boolean Algebra
inferred← citeshttps://doi.org/10.1007/s13160-017-0284-6openalex-snapshot
Autark assignments of Horn CNFs
inferred← citeshttps://doi.org/10.1016/0004-3702(95)00040-2openalex-snapshot
PALO: a probabilistic hill-climbing algorithm
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90250-yopenalex-snapshot
Horn functions and their DNFs
inferred← citeshttps://doi.org/10.1016/0020-0190(93)90178-copenalex-snapshot
A linear time algorithm for unique Horn satisfiability
inferred← citeshttps://doi.org/10.1016/0166-218x(94)90033-7openalex-snapshot
Recognition of q-Horn formulae in linear time
inferred← citeshttps://doi.org/10.1016/b978-1-55860-377-6.50041-4openalex-snapshot
The Challenge of Revising an Impure Theory
inferred← citeshttps://doi.org/10.1016/j.artint.2007.12.003openalex-snapshot
On propositional definability
inferred← citeshttps://doi.org/10.1016/j.camwa.2006.12.094openalex-snapshot
Solving peptide sequencing as satisfiability
inferred← citeshttps://doi.org/10.1016/j.cosrev.2025.100868openalex-snapshot
Backdoors to satisfaction continued
inferred← citeshttps://doi.org/10.1016/j.dam.2003.09.004openalex-snapshot
Consensus algorithms for the generation of all maximal bicliques
inferred← citeshttps://doi.org/10.1016/j.dam.2003.12.011openalex-snapshot
Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
inferred← citeshttps://doi.org/10.1016/j.dam.2004.05.007openalex-snapshot
On the size of maximum renamable Horn sub-CNF
inferred← citeshttps://doi.org/10.1016/j.dam.2007.02.010openalex-snapshot
Satisfiability of mixed Horn formulas
inferred← citeshttps://doi.org/10.1016/j.dam.2014.12.014openalex-snapshot
The Horn renamability, q-Horn and SLUR threshold for random k -CNF formulas
inferred← citeshttps://doi.org/10.1016/j.dam.2015.07.004openalex-snapshot
Trichotomy for integer linear systems based on their sign patterns
inferred← citeshttps://doi.org/10.1016/j.disc.2005.12.033openalex-snapshot
Balanced matrices
inferred← citeshttps://doi.org/10.1016/j.jcss.2024.103520openalex-snapshot
SAT backdoors: Depth beats size
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.04.022openalex-snapshot
Unique key Horn functions
inferred← citeshttps://doi.org/10.1016/j.tcs.2025.115459openalex-snapshot
Computing the D-base and D-relation in finite closure systems
inferred← citeshttps://doi.org/10.1016/j.tcs.2025.115653openalex-snapshot
On the parameterized complexity of diverse SAT
inferred← citeshttps://doi.org/10.1016/s0004-3702(00)00073-4openalex-snapshot
Default reasoning from conditional knowledge bases: Complexity and tractable cases
inferred← citeshttps://doi.org/10.1016/s0004-3702(01)00118-7openalex-snapshot
On functional dependencies in q-Horn theories
inferred← citeshttps://doi.org/10.1016/s0004-3702(98)00107-6openalex-snapshot
The complexity of theory revision
inferred← citeshttps://doi.org/10.1016/s0004-3702(98)00114-3openalex-snapshot
Functional dependencies in Horn theories
inferred← citeshttps://doi.org/10.1016/s0004-3702(99)00088-0openalex-snapshot
On some tractable classes in deduction and abduction
inferred← citeshttps://doi.org/10.1016/s0012-365x(96)00163-xopenalex-snapshot
On perfect 0, ± 1 matrices
inferred← citeshttps://doi.org/10.1016/s0166-218x(00)00262-6openalex-snapshot
Investigations on autark assignments
inferred← citeshttps://doi.org/10.1016/s0166-218x(02)00406-7openalex-snapshot
Lean clause-sets: generalizations of minimally unsatisfiable clause-sets
inferred← citeshttps://doi.org/10.1016/s0166-218x(96)00028-5openalex-snapshot
Variable and term removal from Boolean formulae
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00031-1openalex-snapshot
Maximum renamable Horn sub-CNFs
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00098-0openalex-snapshot
On connected Boolean functions
inferred← citeshttps://doi.org/10.1016/s0743-1066(97)00063-0openalex-snapshot
The horn basis of a set of clauses
inferred← citeshttps://doi.org/10.1016/s0890-5401(02)00012-3openalex-snapshot
Variations on extending partially defined Boolean functions with missing bits
inferred← citeshttps://doi.org/10.1016/s0927-0507(05)12006-4openalex-snapshot
Balanced Matrices
inferred← citeshttps://doi.org/10.1016/s1571-0653(04)00325-7openalex-snapshot
On the use of autarkies for satisfiability decision
inferred← citeshttps://doi.org/10.1023/a:1012820722053openalex-snapshot
Why is Combinational ATPG Efficiently Solvable for Practical VLSI Circuits?
inferred← citeshttps://doi.org/10.1023/a:1018983601518openalex-snapshot
Some interesting research directions in satisfiability
inferred← citeshttps://doi.org/10.1023/a:1023098325064openalex-snapshot
Inferring Minimal Functional Dependencies in Horn and q-Horn Theories
inferred← citeshttps://doi.org/10.1093/logcom/exn069openalex-snapshot
Bottom-up Construction of Semantic Tableaux
inferred← citeshttps://doi.org/10.1109/69.469822openalex-snapshot
Quasi-acyclic propositional Horn knowledge bases: optimal compression
inferred← citeshttps://doi.org/10.1109/dac.1999.781224openalex-snapshot
Why is ATPG easy?
inferred← citeshttps://doi.org/10.1109/hicss.1994.323341openalex-snapshot
Graph-based methods for Horn knowledge compression
inferred← citeshttps://doi.org/10.1137/s0097539792228629openalex-snapshot
A Complexity Index for Satisfiability Problems
inferred← citeshttps://doi.org/10.1145/1284320.1284323openalex-snapshot
On computing all abductive explanations from a propositional Horn theory
inferred← citeshttps://doi.org/10.1145/309847.309857openalex-snapshot
Why is ATPG easy?
inferred← citeshttps://doi.org/10.1145/3655024openalex-snapshot
Strong Backdoors for Default Logic
inferred← citeshttps://doi.org/10.1145/375360.375363openalex-snapshot
Efficient reasoning
inferred← citeshttps://doi.org/10.1287/ijoc.10.3.301openalex-snapshot
An Incremental Branch-and-Bound Method for the Satisfiability Problem
inferred← citeshttps://doi.org/10.1613/jair.1.12006openalex-snapshot
Bounds on the size of PC and URC formulas
inferred← citeshttps://doi.org/10.1613/jair.5658openalex-snapshot
Linear Satisfiability Preserving Assignments
inferred← citeshttps://doi.org/10.24963/ijcai.2018/797openalex-snapshot
Linear Satisfiability Preserving Assignments (Extended Abstract)
inferred← citeshttps://doi.org/10.48550/arxiv.2108.13744openalex-snapshot
The Horn Non-Clausal Class and its Polynomiality
inferred← citeshttps://doi.org/10.5555/777092.777105openalex-snapshot
On computing all abductive explanations
inferred← citeshttps://doi.org/10.70675/22f799bfz3181z4324z8161zb5470bfc9e34openalex-snapshot
Extensions of tractable classes for propositional satisfiability
inferred← citeshttps://doi.org/10.70675/d79e1ec2zb3ffz45b6z9d97za60d60da54f1openalex-snapshot
SAT en Parallèle
inferred← citeshttps://doi.org/10.7282/t3z038hzopenalex-snapshot
A linear programming model for sequential testing
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.