Recognition and dualization of disguised bidual Horn functions

We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual f^d. 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.