Chandru, Vijay ; Coullard, Collette R. ; Hammer, Peter L. ; Montaez, Miguel ; Sun, Xiaorong (1990) On renamable horn and generalized horn functions Annals of Mathematics and Artificial Intelligence, 1 (1-4). pp. 33-47. ISSN 1012-2443
Full text not available from this repository.
Official URL: http://www.springerlink.com/content/w1h55172015751...
Related URL: http://dx.doi.org/10.1007/BF01531069
Abstract
A Boolean function in disjunctive normal form (DNF) is aHorn function if each of its elementary conjunctions involves at most one complemented variable. Ageneralized Horn function is constructed from a Horn function by disjuncting a nested set of complemented variables to it. The satisfiability problem is solvable in polynomial time for both Horn and generalized Horn functions. A Boolean function in DNF is said to berenamable Horn if it is Horn after complementation of some variables. Succinct mathematical characterizations and linear-time algorithms for recognizing renamable Horn and generalized Horn functions are given in this paper. The algorithm for recognizing renamable Horn functions gives a new method to test 2-SAT. Some computational results are also given.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| Keywords: | Computational Logic; Horn Formulae; Generalized Horn Formulae |
| ID Code: | 5468 |
| Deposited On: | 19 Oct 2010 12:12 |
| Last Modified: | 22 Oct 2010 06:31 |
Repository Staff Only: item control page
