Karthik Visweswariah, Sanjeev Kulkarni, et al.
IEEE International Symposium on Information Theory - Proceedings
We give a quadratic algorithm for the following structure identification problem: given a Boolean relation R and a finite set S of Boolean relations, can the relation R be expressed as a conjunctive query over the relations in the set S? Our algorithm is derived by first introducing the concept of a plain basis for a co-clone and then identifying natural plain bases for every co-clone in Post's lattice. In the process, we also give a quadratic algorithm for the problem of finding the smallest co-clone containing a Boolean relation. © 2008 Elsevier Inc. All rights reserved.
Karthik Visweswariah, Sanjeev Kulkarni, et al.
IEEE International Symposium on Information Theory - Proceedings
M. Tismenetsky
International Journal of Computer Mathematics
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
John S. Lew
Mathematical Biosciences