Logical inference and polyhedral projection
If a (medical diagnosis) knowledge base contains atomic propositions \(x_ 1,\dots, x_ n\), and \(x_ 1,\dots, x_ k\) are the disease propositions, then finding all implies propositions that contain no other atoms but \(x_ 1,\dots, x_ k\) is a problem of projecting the knowledge base onto the variables \(x_ 1,\dots, x_ k\), and that is problem closely related to projecting a polyhedron. The main result of the paper is that polyhedral projection obtains precisely the inferences derived by a certain form of unit resolution, called unit \(K\)-resolution, which becomes unit resolution if all atoms in \(x_ 1,\dots, x_ k\) are erased. Unit \(K\)-resolution is proved to completely solve the logical projection problem for Horn clauses, that resolution algorithm is exponential when \(\underline n\) is proportional to \(\underline k\), but (quadratic) polynomial when \(\underline k\) is fixed. A number of new satisfiability algorithms are defined on the basis of polyhedral projection interpretation as inference method in propositional logic. For the entire collection see [Zbl 0772.68004].
- Dynamic Programming, Integral Polyhedra and Horn Clause Knowledge Base
- Polynomial-time inference of all valid implications for Horn and related formulae
- Inference flexibility in Horn clause knowledge bases and the simplex method
- Automated deduction for projection elimination.
- Pseudo-models and propositional Horn inference
- Logic cuts for multilevel generalized assignment problems.
- Logical foundation of the quintuple implication inference methods
- Long range planning in the process industries: A projection approach
- Many-valued logic and mixed integer programming
- Mixed logical-linear programming
- Projection, consistency, and George Boole
- Analyzing read-once cutting plane proofs in Horn systems
- Circumscription and projection as primitives of logic programming
- On the restricted equivalence for subclasses of propositional logic
- scientific article; zbMATH DE number 1894261 (Why is no real title available?)
- Projecting systems of linear inequalities with binary variables
This page was built for publication: Logical inference and polyhedral projection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4202942)