Redundancy in logic II: 2CNF and Horn propositional formulae

We report results about the redundancy of formulae in 2CNF form. In particular, we give a slight improvement over the trivial redundancy algorithm and give some complexity results about some problems related to finding Irredundant Equivalent Subsets (i.e.s.) of 2CNF formulae. The problems of checking whether a 2CNF formula has a unique i.e.s. and checking whether a clause in is all its i.e.s.'s are polynomial. Checking whether a 2CNF formula has an i.e.s. of a given size and checking whether a clause is in some i.e.s.'s of a 2CNF formula are polynomial or NP-complete depending on whether the formula is cyclic. Some results about Horn formulae are also reported.     

Redundancy in logic I: CNF propositional formulae

A knowledge base is redundant if it contains parts that can be inferred from the rest of it. We study some problems related to the redundancy of a CNF formula. In particular, any CNF formula can be made irredundant by deleting some of its clauses: what results is an irredundant equivalent subset. We study the complexity of problems related to irredundant equivalent subsets: verification, checking existence of an irredundant equivalent subset with a given size, checking necessary and possible presence of clauses in irredundant equivalent subsets, and uniqueness. We also consider the problem of redundancy with different definitions of equivalence.     

Horn minimization by iterative decomposition

Given a Horn CNF representing a Boolean function f, the problem of Horn minimization consists in constructing a CNF representation off which has a minimum possible number of clauses. This problem is the formalization of the problem of knowledge compression for speeding up queries to propositional Horn expert systems, and it is known to be NP-hard. In this paper we present a linear time algorithm which takes a Horn CNF as an input, and through a series of decompositions reduces the minimization of the input CNF to the minimization problem on a“shorter” CNF. The correctness of this decomposition algorithm rests on several interesting properties of Horn functions which, as we prove here, turn out to be independent of the particular CNF representations. This revised version was published online in June 2006 with corrections to the Cover Date.     

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

This paper investigates the complexity of a general inference problem: given a propositional formula in conjunctive normal form, find all prime implications of the formula. Here, a prime implication means a minimal clause whose validity is implied by the validity of the formula. We show that, under some reasonable assumptions, this problem can be solved in time polynomially bounded in the size of the input and in the number of prime implications. In the case of Horn formulae, the result specializes to yield an algorithm whose complexity grows only linearly with the number of prime implications. The result also applies to a class of formulae generalizing both Horn and quadratic formulae.To the memory of Robert G. Jeroslow     

Fast approximate energy minimization via graph cuts

Many tasks in computer vision involve assigning a label (such as disparity) to every pixel. A common constraint is that the labels should vary smoothly almost everywhere while preserving sharp discontinuities that may exist, e.g., at object boundaries. These tasks are naturally stated in terms of energy minimization. The authors consider a wide class of energies with various smoothness constraints. Global minimization of these energy functions is NP-hard even in the simplest discontinuity-preserving case. Therefore, our focus is on efficient approximation algorithms. We present two algorithms based on graph cuts that efficiently find a local minimum with respect to two types of large moves, namely expansion moves and swap moves. These moves can simultaneously change the labels of arbitrarily large sets of pixels. In contrast, many standard algorithms (including simulated annealing) use small moves where only one pixel changes its label at a time. Our expansion algorithm finds a labeling within a known factor of the global minimum, while our swap algorithm handles more general energy functions. Both of these algorithms allow important cases of discontinuity preserving energies. We experimentally demonstrate the effectiveness of our approach for image restoration, stereo and motion. On real data with ground truth, we achieve 98 percent accuracy     

Theoretical justification of approximate norm minimization method for intelligent digital redesign

This paper investigates the theoretical justification of intelligent digital redesign (IDR) methods based on the approximate discrete-time models. Its main purpose is to design the digital fuzzy controller achieving the minimum norm distance between the trajectories of the approximate closed-loop systems under the analog and the digital controls. It is verified that, if there exist the digital gains such that the approximate norm distance is sufficiently small, the redesigned controller makes the trajectories of the exact closed-loop systems close, or, at least, asymptotically stabilizes the plant.     

Matrix formulae for open and closed-loop approximate model matching in frequency domain

This paper concerns model matching of SISO systems in the frequency domain. The matching uses Pade coefficients and Markov parameters of a reference model of which the final system will be an approximation. Because the matching is approximate, constraints on the structures of both the reference model and the final system can be somewhat relaxed. In this paper an easy-to-implement matrix formulation is derived for both open- and closed-loop matching problems. Some results concerning pole-zero cancellations are presented, along with a number of numerical examples provided to illustrate the usefulness and simplicity of the approach.     

Hardness results for neural network approximation problems

We consider the problem of efficiently learning in two-layer neural networks. We investigate the computational complexity of agnostically learning with simple families of neural networks as the hypothesis classes. We show that it is NP-hard to find a linear threshold network of a fixed size that approximately minimizes the proportion of misclassified examples in a training set, even if there is a network that correctly classifies all of the training examples. In particular, for a training set that is correctly classified by some two-layer linear threshold network with k hidden units, it is NP-hard to find such a network that makes mistakes on a proportion smaller than c/k² of the examples, for some constant c. We prove a similar result for the problem of approximately minimizing the quadratic loss of a two-layer network with a sigmoid output unit.     

Hardness and approximation results for packing steiner trees

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee ofO (√n logn), wheren denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of Θ(m ^1/3/−ɛ) and give an approximation guarantee ofO(m ^1/2/+ɛ), wherem denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs. Supported by NSERC Grant No. OGP0138432. Supported by an NSERC postdoctoral fellowship, Department of Combinatorics and Optimization at University of Waterloo, and a University start-up fund at University of Alberta.     

An Inplementation of Pure Horn Clause Logic Programming in a Reduction System

Many reduction systems have been presented for implementing functional programming languages.We propose here an extension of a reduction architecture to realize a kind of logic programming-pure Horn clause logic programming.This is an attempt to approach amalgamation of the two important programming paradigms.     

Global optimality of approximate dynamic programming and its use in non-convex function minimization

This study investigates the global optimality of approximate dynamic programming (ADP) based solutions using neural networks for optimal control problems with fixed final time. Issues including whether or not the cost function terms and the system dynamics need to be convex functions with respect to their respective inputs are discussed and sufficient conditions for global optimality of the result are derived. Next, a new idea is presented to use ADP with neural networks for optimization of non-convex smooth functions. It is shown that any initial guess leads to direct movement toward the proximity of the global optimum of the function. This behavior is in contrast with gradient based optimization methods in which the movement is guided by the shape of the local level curves. Illustrative examples are provided with single and multi-variable functions that demonstrate the potential of the proposed method.     

Hardness results for covering arrays avoiding forbidden edges and error-locating arrays

Covering arrays avoiding forbidden edges (CAFEs) are used in testing applications (software, networks, circuits, drug interaction, material mixtures, etc.) where certain combinations of parameter values are forbidden. Danziger et al. (2009) [8] have studied this problem and shown some computational complexity results. Around the same time, Martinez et al. (2009) [19] defined and studied error-locating arrays (ELAs), which are closely related to CAFEs. Both papers left some computational complexity questions. In particular, these papers showed polynomial-time solvability of the existence of CAFEs and ELAs for binary alphabets (g=2), and the NP-hardness of these problems for g≥5. In this paper, we prove that optimizing CAFEs and ELAs is indeed NP-hard even when restricted to the case of binary alphabets, using a reduction from edge clique covers of graphs (ECCs). We also provide a hardness of approximation result. We explore important relationships between ECCs and CAFEs and give some new bounds for uniform ECCs and CAFEs.     

Horn axiomatizations for sequential data

We propose a notion of deterministic association rules for ordered data. We prove that our proposed rules can be formally justified by a purely logical characterization, namely, a natural notion of empirical Horn approximation for ordered data which involves background Horn conditions; these ensure the consistency of the propositional theory obtained with the ordered context. The whole framework resorts to concept lattice models from Formal Concept Analysis, but adapted to ordered contexts. We also discuss a general method to mine these rules that can be easily incorporated into any algorithm for mining closed sequences, of which there are already some in the literature.     

An efficient algorithm for Horn description

We give a new algorithm for computing a prepositional Horn CNF formula given the set of its models. Its running time is O(|R|n(|R|+n)), where |R| is the number of models and n that of variables, and the computed CNF contains at most |R|n clauses. This algorithm also uses the well-known closure property of Horn relations in a new manner.     

Question-asking strategies for Horn clause systems

An expert system applies the deduction rules in its knowledge base to a set of initial data to reach a conclusion. When the initial data are insufficient, the expert system may ask the user for additional information. This paper analyzes effectiveness and efficiency of question-asking strategies in expert systems with Horn clause knowledge bases. An effective strategy reaches a conclusion after asking as few questions as possible. An efficient strategy can be computed quickly. We prove that effective strategies are, unfortunately, not efficient. However, we present a somewhat less effective but very efficient strategy. It employs an algorithm which simultaneously performs deduction and question selection in log-linear time.Supported in part by NSF grant DMS-8513970.