𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Difference of Horn Theories

✍ Scribed by Thomas Eiter; Toshihide Ibaraki; Kazuhisa Makino

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
248 KB
Volume
61
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we consider computing the difference between two Horn theories. This problem may arise, for example, if we take care of a theory change in a knowledge base. In general, the difference of Horn theories is not Horn. Therefore, we consider Horn approximations of the difference in terms of Horn cores (i.e., weakest Horn theories included in the difference) and the Horn envelope (i.e., the strongest Horn theory containing the difference), which have been proposed and analyzed extensively in the literature. We study the problem under the familiar representation of Horn theories by Horn CNFs, as well as under the recently proposed model-based representation in terms of the characteristic models. For all problems and representations, polynomial time algorithms or proofs of intractability for the propositional case are provided; thus, our work gives a complete picture of the tractability intractability frontier in the propositional Horn theories.

πŸ“œ SIMILAR VOLUMES

ON THE HORN EFFECT OF A TYRE/ROAD INTERF
ON THE HORN EFFECT OF A TYRE/ROAD INTERFACE, PART II: ASYMPTOTIC THEORIES
✍ C.-Y. KUO; R.A.G. GRAF; A.P. DOWLING; W.R. GRAHAM πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 210 KB

In Part I, it was shown that boundary element method calculations could successfully be applied to determine sound ampli"cation by a tyre/road geometry. However, the computations are expensive, limited to frequencies below 2500 Hz, and provide little physical insight. In Part II, two supplementary a

The Essentially Equational Theory of Hor
The Essentially Equational Theory of Horn Classes
✍ Hans-E. Porst πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 233 KB

It is well known that the model categories of universal Horn theories are locally presentable, hence essentially algebraic (see ). In the special case of quasivarieties a direct translation of the implicational syntax into the essentially equational one is known (see ). Here we present a similar tr

On the Bateman–Horn Conjecture
On the Bateman–Horn Conjecture
✍ Stephan Baier πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 156 KB

If f 1 ðnÞ; . . . ; f r ðnÞ are all prime for infinitely many n; then it is necessary that the polynomials f i are irreducible in Z½X ; have positive leading coefficients, and no prime p divides all values of the product f 1 ðnÞ Á Á Á f r ðnÞ; as n runs over Z: Assuming these necessary conditions, B

On the Theories of Triangular Sets
On the Theories of Triangular Sets
✍ Philippe Aubry; Daniel Lazard; Marc Moreno Maza πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 354 KB

Different notions of triangular sets are presented. The relationship between these notions are studied. The main result is that four different existing notions of good triangular sets are equivalent.