On renamable Horn and generalized Horn functions |
| |
Authors: | Vijaya Chandru Collette R Coullard Peter L Hammer Miguel Montañez Xiaorong Sun |
| |
Affiliation: | (1) School of Industrial Engineering, Purdue University, 47907 West Lafayette, IN, USA;(2) RUTCOR-Rutgers Center for Operations Research, Rutgers University, 08903 New Brunswick, NJ, USA |
| |
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.The authors were supported in part by the Office of Naval Research under University Research Initiative grant number N00014-86-K-0689. Chandru was also supported by NSF grant number DMC 88-07550.The authors gratefully acknowledge the partial support of NSF (Grant DMS 89-06870) and AFOSR (Grant 89-0066 and 89-0512). |
| |
Keywords: | Computational logic Horn formulae generalized Horn formulae |
本文献已被 SpringerLink 等数据库收录! |