On renamable horn and generalized horn functions

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


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