Structure identification of Boolean relations and plain bases for co-clones

被引：27

作者：

Creignou, Nadia ^{[2
]}

Kolaitis, Phokion ^{[3
]}

Zanuttini, Bruno ^{[1
]}

机构：

[1] Univ Caen, GREYC, UMR CNRS 6072, F-14032 Caen, France

[2] Univ Miditerranee, LIF, UMR CNRS 6166, F-13288 Marseille, France

[3] IBM Almaden Res Ctr, San Jose, CA 95120 USA

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2008年 / 74卷 / 07期

关键词：

Computational complexity; Boolean constraints; Closure properties; Boolean co-clones; Inverse satisfiability;

D O I：

10.1016/j.jcss.2008.02.005

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：1103 / 1115

页数：13

共 50 条

[1] Bases for Boolean co-clones
Böhler, E
Reith, S
Schnoor, H
Vollmer, H
INFORMATION PROCESSING LETTERS, 2005, 96 (02) : 59 - 66
[2] Weak bases of Boolean co-clones
Lagerkvist, Victor
INFORMATION PROCESSING LETTERS, 2014, 114 (09) : 462 - 468
[3] Frozen Boolean partial co-clones
Nordh, Gustav
Zanuttini, Bruno
ISMVL: 2009 39TH IEEE INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC, 2009, : 120 - +
[4] On Hyper Co-clones
Colic, Jelena
Machida, Hajime
Pantovic, Jovanka
2013 IEEE 43RD INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2013), 2013, : 182 - 185
[5] Polynomially Closed Co-Clones
Lagerkvist, Victor
Wahlstroem, Magnus
2014 IEEE 44TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2014), 2014, : 85 - 90
[6] Weak bases for Boolean relational clones revisited
Behrisch, Mike
2022 IEEE 52ND INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2022), 2022, : 68 - 73
[7] C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases
Lagerkvist, Victor
Roy, Biman
JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING, 2022, 38 (3-4) : 333 - 353
[8] Boolean Max-Co-Clones
Bulatov, Andrei A.
2013 IEEE 43RD INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2013), 2013, : 192 - 197
[9] Boolean max-co-clones
Bulatov, Andrei A.
ALGEBRA UNIVERSALIS, 2015, 74 (1-2) : 139 - 162
[10] Boolean max-co-clones
Andrei A. Bulatov
Algebra universalis, 2015, 74 : 139 - 162

← 1 2 3 4 5 →