𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Semantical and computational aspects of Horn approximations

✍ Scribed by Marco Cadoli; Francesco Scarcello

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
152 KB
Volume
119
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

✦ Synopsis

Selman and Kautz proposed a method, called Horn approximation, for speeding up inference in propositional Knowledge Bases. Their technique is based on the compilation of a propositional formula into a pair of Horn formulae: a Horn Greatest Lower Bound (GLB) and a Horn Least Upper Bound (LUB). In this paper we focus on GLBs and address two questions that have been only marginally addressed so far:

(1) what is the semantics of the Horn GLBs?

(2) what is the exact complexity of finding them? We obtain semantical as well as computational results. The major semantical result is: The set of minimal models of a propositional formula and the set of minimum models of its Horn GLBs are the same. The major computational result is: Finding a Horn GLB of a propositional formula in CNF is NP-equivalent.

πŸ“œ SIMILAR VOLUMES

Optimal compression of propositional Hor
Optimal compression of propositional Horn knowledge bases: complexity and approximation
✍ Peter L. Hammer; Alexander Kogan πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 746 KB

Hammer, P.L. and A. Kogan, Optimal compression of propositional Horn knowledge bases: complexity and approximation (Research Note), Artificial Intelligence 64 (1993) 131-145. Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the probl

Restricted Hartree–Fock approximation. I
Restricted Hartree–Fock approximation. II. Computational aspects of the direct minimization procedure
✍ J. ÁNdez Fern Rico; M. Paniagua; J. I. ÁNdez Fern Alonso; P. Fantucci πŸ“‚ Article πŸ“… 1983 πŸ› John Wiley and Sons 🌐 English βš– 624 KB

## Abstract A RHF energy minimization procedure based on the treatment outlined in Part I of this series of articles is presented. Test calculations performed on several closed‐ and open‐shell systems show that the present procedure is definitely superior to the conventional SCF methods. In particu

Behavioral and computational aspects of
Behavioral and computational aspects of language and its acquisition
✍ Shimon Edelman; Heidi Waterfall πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 683 KB

One of the greatest challenges facing the cognitive sciences is to explain what it means to know a language, and how the knowledge of language is acquired. The dominant approach to this challenge within linguistics has been to seek an efficient characterization of the wealth of documented structural