On deciding subsumption problems

Subsumption is an important redundancy elimination method in automated deduction. A clause D is subsumed by a set of clauses if there is a clause C and a substitution such that the literals of C are included in D. In the field of automated model building, subsumption has been modified to an even stronger redundancy elimination method, namely the so-called clausal H-subsumption. Atomic H-subsumption emerges from clausal H-subsumption by restricting D to an atom and to a set of atoms. Both clausal and atomic H-subsumption play an indispensable key role in automated model building. Moreover, problems equivalent to atomic H-subsumption have been studied with different terminologies in many areas of computer science. Both clausal and atomic H-subsumption are known to be intractable, i.e., _p ² -complete and NP-complete, respectively. In this paper, we present a new approach to deciding (clausal and atomic) H-subsumption that is based on a reduction to QSAT₂ and SAT, respectively.This was partially supported by the Austrian Science Foundation under grant P15068. We thank the anonymous referees for valuable comments.     

On subsumption in distributed derivations

In this paper we study the subsumption inference rule in the context of distributed deduction. It is well known that the unrestricted application of subsumption may destroy the fairness and thus the completeness of a deduction strategy. Solutions to this problem in sequential theorem proving are known. We observe that in distributed automated deduction, subsumption may also thwartmonotonicity, a dual property of soundness, in addition to completeness. Not only do the solutions for the sequential case not apply, even proper subsumption may destroy monotonicity in the distributed case.We present these problems and propose a general solution that treats subsumption as a composition of a replacement inference rule,replacement subsumption, and a deletion inference rule,variant subsumption. (Proper subsumption, in this case, becomes a derived inference rule.) We define a newdistributed subsumption inference rule, which has all the desirable properties: it allows subsumption, including subsumption of variants, in a distributed derivation, while preserving fairness and monotonicity. It also works in both sequential and distributed environments.We conclude the paper with some discussion of the different behavior of subsumption in different architectures.     

On deciding subsumption problems

Subsumption is an important redundancy elimination method in automated deduction. A clause D is subsumed by a set C of clauses if there is a clause CC and a substitution such that the literals of C are included in D. In the field of automated model building, subsumption has been modified to an even stronger redundancy elimination method, namely the so-called clausal H-subsumption. Atomic H-subsumption emerges from clausal H-subsumption by restricting D to an atom and C to a set of atoms. Both clausal and atomic H-subsumption play an indispensable key role in automated model building. Moreover, problems equivalent to atomic H-subsumption have been studied with different terminologies in many areas of computer science. Both clausal and atomic H-subsumption are known to be intractable, i.e., ₂ ^p -complete and NP-complete, respectively. In this paper, we present a new approach to deciding (clausal and atomic) H-subsumption that is based on a reduction to QSAT₂ and SAT, respectively.     

The subsumption lattice and query learning

The paper identifies several new properties of the lattice induced by the subsumption relation over first-order clauses and derives implications of these for learnability. In particular, it is shown that the length of subsumption chains of function free clauses with bounded size can be exponential in the size. This suggests that simple algorithmic approaches that rely on repeating minimal subsumption-based refinements may require a long time to converge. It is also shown that with bounded size clauses the subsumption lattice has a large branching factor. This is used to show that the class of first-order length-bounded monotone clauses is not properly learnable from membership queries alone. Finally, the paper studies pairing, a generalization operation that takes two clauses and returns a number of possible generalizations. It is shown that there are clauses with an exponential number of pairing results which are not related to each other by subsumption. This is used to show that recent pairing-based algorithms can make exponentially many queries on some learning problems.     

Abstraction and subsumption in modular verification of C programs

Formal Methods in System Design - The type-theoretic notions of existential abstraction, subtyping, subsumption, and intersection have useful analogues in separation-logic proofs of imperative...     

On the discovery of subsumption relations for the alignment of ontologies

For the effective alignment of ontologies, the subsumption mappings between the elements of the source and target ontologies play a crucial role, as much as equivalence mappings do. This paper presents the “Classification-Based Learning of Subsumption Relations” (CSR) method for the alignment of ontologies. Given a pair of two ontologies, the objective of CSR is to learn patterns of features that provide evidence for the subsumption relation among concepts, and thus, decide whether a pair of concepts from these ontologies is related via a subsumption relation. This is achieved by means of a classification task, using state of the art supervised machine learning methods. The paper describes thoroughly the method, provides experimental results over an extended version of benchmarking series of both artificially created and real world cases, and discusses the potential of the method.     

Inference engine greediness: subsumption and suboptimality

Greedy inference engines find solutions without a complete enumeration of all solutions. Instead, greedy algorithms search only a portion of the rule set in order to generate a solution. As a result, using greedy algorithms results in some unique system verification and quality concerns. This paper focuses on mitigating the impact of those concerns. In particular, rule orderings are established so that better solutions can be found first and those rules that would never be examined by greedy inference engines can be identified. The primary results are driven by rule specificity. A rule is more specific than some other rule when the conditions in one rule are a subset of the conditions in another rule. If the least specific rule is ordered first and it is true, then greedy algorithms will never get to the more specific rule, even if they are true. Since the more specific rules generally also have the greatest return this results in the `wrong' ordering—the rule with the least return will be found. As a result, this paper focuses on generating orderings that will likely lead to higher returns.     

Fixpoint iteration with subsumption in deductive databases

Declarative languages for deductive and object-oriented databases require some high-level mechanism for specifying semantic control knowledge. This paper proposes user-supplied subsumption information as a paradigm to specify desired, prefered or useful deductions at the meta level. For this purpose we augment logic programming by subsumption relations and succeed to extend the classical theorems for least models, fixpoints and bottom-up evaluation accordingly. Moreover, we provide a differential fixpoint operator for efficient query evaluation in deductive databases. This operator discards subsumed tuples on the fly. We also exemplify the ease of use of this programming methodology. In particular, we demonstrate how heuristic AI search procedures can be integrated into deductive databases in this way.This article is a revised and extended version of (Köstler et al., 1993)     

On pseudo-BL algebras and BCC-algebras

We further study the filter theory of pseudo-BL algebras. We give some equivalent conditions of filter, normal filter and Boolean filter. We introduce the notion of pseudo MV-filter, pseudo-G filter and characterize Boolean algebras, pseudo-MV algebras and pseudo Gödel algebras (i.e. Gödel algebras) in pseudo-BL algebras. We establish the connections between BCC-algebras, pseudo-BCK algebras, pseudo-BL algebras and weak pseudo-BL algebras (pseudo-MTL algebras).     

Inverse subsumption for complete explanatory induction

Modern explanatory inductive logic programming methods like Progol, Residue procedure, CF-induction, HAIL and Imparo use the principle of inverse entailment (IE). Those IE-based methods commonly compute a hypothesis in two steps: by first constructing an intermediate theory and next by generalizing its negation into the hypothesis with the inverse of the entailment relation. Inverse entailment ensures the completeness of generalization. On the other hand, it imposes many non-deterministic generalization operators that cause the search space to be very large. For this reason, most of those methods use the inverse relation of subsumption, instead of entailment. However, it is not clear how this logical reduction affects the completeness of generalization. In this paper, we investigate whether or not inverse subsumption can be embedded in a complete induction procedure; and if it can, how it is to be realized. Our main result is a new form of inverse subsumption that ensures the completeness of generalization. Consequently, inverse entailment can be reduced to inverse subsumption without losing the completeness for finding hypotheses in explanatory induction.     

CLASP: integrating term subsumption systems and production systems

The general architecture and an implementation of a classification-based production system (CLASP) are presented. The main objective is to extend the benefits of classification capabilities in frame systems to the developers of rule-based systems. Two major processes of CLASP, a semantic pattern matcher and a pattern classifier, are described. The semantic pattern matcher extends the pattern matching capabilities of rule-based systems through the use of terminological knowledge. The pattern classifier enables the system to compute a rule's specificity, which is useful for conflict resolution, based on the semantics of its left-hand side. The paradigm not only enhances the reasoning capabilities of rule-based systems, but also helps to reduce the cost of maintaining such systems because definitional knowledge is explicitly represented in a form that facilitates sharing and minimizes duplication of effort     

On algebras having displacement structure

We discuss some results concerning the problem of the location of the algebras contained in a matrix space with displacement structure.     

On possibility and probability measures in finite Boolean algebras

 In this paper, we study what possibility and necessity measures are like in a finite Boolean algebra, establishing a classification of possibility measures in this type of algebras. The relation between probability and possibility measures is studied. Some conditions for obtaining probabilities that are coherent with a possibility are given. Lastly, Euclidean distance is used for finding probabilities that are close to a given possibility. Also the closest probability is identified and turns out to be coherent. RID="*" ID="*" Research funded by CICYT (Spain) under projects PB98-1379-C02-02 and TIC00-1420. Authors wish to thank an anonymous referee whose comments and information helped them to improve this paper.     

On effect algebras of fuzzy sets

We introduce the category IE of effect algebras of fuzzy sets and sequentially continuous effect homomorphisms and describe its fundamental properties. We show that IE and the category ID of D-posets of fuzzy sets are isomorphic, hence the constructions and properties of ID related to applications to probability theory are valid for the corresponding effect algebras. We describe basic properties of categorical coproducts in ID and dually of categorical products in the corresponding category MID of measurable spaces. We end with remarks on fuzzy probability notions. Supported by VEGA Grant 1/2002/05.     

On rational definitions in complete algebras without rank

Algebras without rank are suggested in order to simplify the algebraic treatment of control structures. The regular and equational normal forms of rational schemes are proved without using any representation of finite or infinite trees.