Recognition and dualization of disguised bidual Horn functions |
| |
Authors: | Thomas Eiter Toshihide Ibaraki |
| |
Affiliation: | a Institut für Informationssysteme, Technische Universität Wien, Favoritenstraße 9-11, A-1040 Wien, Austria b Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan c Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531, Japan |
| |
Abstract: | We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual fd. While this problem is not solvable in quasi-polynomial total time in general (unless SAT is solvable in quasi-polynomial time), it is so in case the input belongs to special classes, e.g., the class of bidual Horn CNF ? Discrete Appl. Math. 96-97 (1999) 55-88] (i.e., both ? and its dual ?d represent Horn functions). In this paper, we show that a disguised bidual Horn CNF ? (i.e., ? becomes a bidual Horn CNF after renaming of variables) can be recognized in polynomial time, and its dualization can be done in quasi-polynomial total time. We also establish a similar result for dualization of prime CNFs. |
| |
Keywords: | Algorithms Output-polynomial Boolean function Dualization Horn function Bidual Horn function |
本文献已被 ScienceDirect 等数据库收录! |
|