Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 11 of 11
Full-Text Articles in Entire DC Network
A Partial Instantiation Based First Order Theorem Prover, Vijay Chandru, John N. Hooker, Anjul Shrivastava, Gabriela Rago
A Partial Instantiation Based First Order Theorem Prover, Vijay Chandru, John N. Hooker, Anjul Shrivastava, Gabriela Rago
John Hooker
Satisfiability algorithms for propositional logic have improved enormously in recent years. This increases the attractiveness of satisfiability methods for first order logic that reduce the problem to a series of ground-level satisfiability problems. Partial Instantiation for first order satisfiability differs radically from standard resolution based methods. Two approaches to partial instantiation based first order theorem provers have been studied by R. Jeroslow and by Plaisted and Zhu. Hooker and Rago have described improvements of Jeroslow's approach by a) extending it to logic with functions b) accelerating it through use of satisfiers as introduced by Gallo and Rago, and c) simplifying …
Predicting Cause-Effect Relationships From Incomplete Discrete Observations, E Boros, P. L. Hammer, John N. Hooker
Predicting Cause-Effect Relationships From Incomplete Discrete Observations, E Boros, P. L. Hammer, John N. Hooker
John Hooker
This paper addresses a prediction problem occurring frequently in practice. The problem consists in predicting the value of a function on the basis of discrete observational data that are incomplete in two senses. Only certain arguments of the function are observed, and the function value is observed only for certain combinations of values of these arguments. The problem is considered under a monotonicity condition that is natural in many applications. Applications to tax auditing, medicine, and real estate valuation are discussed. In particular, a special class of problems is identified for which the best monotone prediction can be found in …
Partial Instantiation Methods For Inference In First-Order Logic, John N. Hooker, G. Rago, V. Chandru, A. Shrivastava
Partial Instantiation Methods For Inference In First-Order Logic, John N. Hooker, G. Rago, V. Chandru, A. Shrivastava
John Hooker
Satisfiability algorithms for propositional logic have improved enormously in recently years. This improvement increases the attractiveness of satisfiability methods for first-order logic that reduce the problem to a series of ground-level satisfiability problems. R. Jeroslow introduced a partial instantiation method of this kind that differs radically from the standard resolution-based methods. This paper lays the theoretical groundwork for an extension of his method that is general enough and efficient enough for general logic programming with indefinite clauses. In particular we improve Jeroslow's approach by (1) extending it to logic with functions, (2) accelerating it through the use of satisfiers, as …
Boolean Regression, E. Boros, P. L. Hammer, John N. Hooker
Boolean Regression, E. Boros, P. L. Hammer, John N. Hooker
John Hooker
We take a regression-based approach to the problem of induction, which is the problem of inferring general rules from specific instances. Whereas traditional regression analysis fits a numerical formula to data, we fit a logical formula to boolean data. We can, for instance, construct an expert system for fitting rules to an expert's observed behavior. A regression-based approach has the advantage of providing tests of statistical significance as well as other tools of regression analysis. Our approach can be extended to nonboolean discrete data, and we argue that it is better suited to rule construction than logit and other types …
Optimization Methods In Logic, John N. Hooker
Optimization Methods In Logic, John N. Hooker
John Hooker
Optimization can make at least two contributions to boolean logic. Its solution methods can address inference and satisfiability problems, and its style of analysis can reveal tractable classes of boolean problems that might otherwise have gone unnoticed.
Mathematical Programming Methods For Reasoning Under Uncertainty, John N. Hooker
Mathematical Programming Methods For Reasoning Under Uncertainty, John N. Hooker
John Hooker
We survey three applications of mathematical programming to reasoning under uncertainty: a) an application of linear programming to probabilistic logic, b) an application of nonlinear programming to Bayesian logic, a combination of Bayesian inference with probabilistic logic and c) an application of integer programming to Dempster-Shafer theory, which is a method of combining evidence from diffierent sources
Logical Inference And Polyhedral Projection, John N. Hooker
Logical Inference And Polyhedral Projection, John N. Hooker
John Hooker
We explore connections between polyhedral projection and inference in propositional logic. We formulate the problem of drawing all inferences that contain a restricted set of atoms (i.e., all inferences that pertain to a given question) as a logical projection problem. We show that polyhedral projection partially solves this problem and in particular derives precisely those inferences that can be obtained by a certain form of unit resolution. We prove that this unit resolution algorithm is exponential in the number of atoms in the restricted set but is polynomial in the problem size when this number of fixed. We also survey …
Branching Rules For Satisfiability, John N. Hooker, V. Vinay
Branching Rules For Satisfiability, John N. Hooker, V. Vinay
John Hooker
Recent experience suggests that branching algorithms are among the most attractive for solving propositional satisfiability problems. A key factor in their success is the rule they use to decide on which variable to branch next. We attempt to explain and improve the performance of branching rules with an empirical model-building approach. One model is based on the rationale given for the Jeroslow-Wang rule, variations of which have performed well in recent work. The model is refuted by carefully designed computational experiments. A second model explains the success of the Jeroslow-Wang rule, makes other predictions confirmed by experiment, and leads to …
New Methods For Computing Inferences In First Order Logic, John N. Hooker
New Methods For Computing Inferences In First Order Logic, John N. Hooker
John Hooker
Recent improvements in satisfiability algorithms for propositional logic have made partial instantiation methods for first order predicate logic computationally more attractive. Two such methods have been proposed, one by Jeroslow and a hypergraph method for datalog formulas by Gallo and Rago. We show that they are instances of two general approaches to partial instantiation, and we develop these approaches for a large decidable fragment of first order logic (the ∃∀ fragment).
Determining Lower And Upper Bounds On Probabilities Of Atomic Propositions In Sets Of Logical Formulas Represented By Digraphs, K. A. Andersen, John N. Hooker
Determining Lower And Upper Bounds On Probabilities Of Atomic Propositions In Sets Of Logical Formulas Represented By Digraphs, K. A. Andersen, John N. Hooker
John Hooker
In this paper we consider the problem of determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs. We establish a sharp upper bound, as well as a lower bound that is not in general sharp. We show further that under a certain condition the lower bound is sharp. In that case, we obtain a closed form solution for the possible probabilities of the atomic propositions.
Detecting Embedded Horn Structure In Propositional Logic, V. Chandru, John N. Hooker
Detecting Embedded Horn Structure In Propositional Logic, V. Chandru, John N. Hooker
John Hooker
We show that the problem of finding a maximum renamable Horn problem within a propositional satisfiability problem is NP-hard but can be formulated as a set packing and therefore a maximum clique problem, for which numerous algorithms and heuristics have been developed.