Open Access. Powered by Scholars. Published by Universities.®
- File Type
Articles 1 - 16 of 16
Full-Text Articles in Industrial Organization
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.
Tight Representation Of Logical Constraints As Cardinality Rules, John Hooker, Hong Yan
Tight Representation Of Logical Constraints As Cardinality Rules, John Hooker, Hong Yan
John Hooker
We address the problem of finding a "tight" representation of complex logical constraints in a mixed integer programming model by describing a convex hull representation of cardinality rules.
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 …
A Linear Programming Framework For Logics Of Uncertainty, K. Andersen, John Hooker
A Linear Programming Framework For Logics Of Uncertainty, K. Andersen, John Hooker
John Hooker
Several logics for reasoning under uncertainty distribute “probability mass” over sets in some sense. These include probabilistic logic, Dempster-Shafer theory, other logics based on belief functions, and second-order probabilistic logic. We show that these logics are instances of a certain type of linear programming model, typically with exponentially many variables. We also show how a single linear programming package can implement these logics computationally if one “plugs in” a different column generation subroutine for each logic, although the practicality of this approach has been demonstrated so far only for probabilistic logic.
Solving The Incremental Satisfiability Problem, John Hooker
Solving The Incremental Satisfiability Problem, John Hooker
John Hooker
Given a set of clauses in propositional logic that have been found satisfiable, we wish to check whether satisfiability is preserved when the clause set is incremented with a new clause. We describe an efficient implementation of the Davis-Putnam-Loveland algorithm for checking the satisfiability of the original set. We then show how to modify the algorithm for efficient solution of the incremental problem, which is NP-complete. We also report computational results.
Resolution And The Integrality Of Satisfiability Problems, John Hooker
Resolution And The Integrality Of Satisfiability Problems, John Hooker
John Hooker
No abstract provided.
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.
Probabilistic Logic For Belief Nets, K. Andersen, John Hooker
Probabilistic Logic For Belief Nets, K. Andersen, John Hooker
John Hooker
We describe how to combine probabilistic logic and Bayesian networks to obtain a new frame-work ("Bayesian logic") for dealing with uncertainty and causal relationships in an expert system. Probabilistic logic, invented by Boole, is a technique for drawing inferences from uncertain propositions for which there are no independence assumptions. A Bayesian network is a "belief net" that can represent complex conditional independence assumptions. We show how to solve inference problems in Bayesian logic by applying Benders decomposition to a nonlinear programming formulation. We also show that the number of constraints grows only linearly with the problem size for a large …
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.