Tractability and learnability arising from algebras with few subpowers

被引：29

作者：

Idziak, Pawel ^{[1
]}

Markovic, Petar ^{[2
]}

McKenzie, Ralph ^{[3
]}

Valeriote, Matthew ^{[4
]}

Willard, Ross ^{[5
]}

机构：

[1] Jagiellonian Univ, Theoret Com Sci Dept, Krakow, Poland

[2] Univ Novi Sad, Dept Math & Informat, YU-21000 Novi Sad, Serbia

[3] Vanderbilt Univ, Dept Math, Nashville, TN USA

[4] McMaster Univ, Dept Math & Stat, Hamilton, ON L8S 4L8, Canada

[5] Univ Waterloo, Dept Pure Math, Waterloo, ON N2L 3G1, Canada

来源：

22ND ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS | 2007年

关键词：

D O I：

10.1109/LICS.2007.50

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A k-edge operation V on a finite set A is a k + 1 -ary operation that satisfies the identities [GRAPHICS] We prove that any constraint language F that, for some k > 1, has a k-edge operation as a polymorphism is globally tractable. We also show that the set of relations definable over IF using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries. Special instances of k-edge operations are Mal'cev and near-unanimiry operations and so this class of constraint languages includes many well known examples.

引用

页码：213 / +

页数：2

共 21 条

[1] WHEN WONT MEMBERSHIP QUERIES HELP [J].

ANGLUIN, D ;

KHARITONOV, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 50 (02) :336-355

[2]

ANGLUIN D, 1991, 23 S THEOR COMP NEW

[3]

BERMAN J, 2006, VARIETIES FEW SUBALG

[4] Classifying the complexity of constraints using finite algebras [J].

Bulatov, A ;

Jeavons, P ;

Krokhin, A .

SIAM JOURNAL ON COMPUTING, 2005, 34 (03) :720-742

[5]

BULATOV A, UNPUB ALGEBRAIC STRU

[6]

BULATOV A, IN PRESS THEORETICAL

[7] A dichotomy theorem for constraint satisfaction problems on a 3-element set [J].

Bulatov, AA .

JOURNAL OF THE ACM, 2006, 53 (01) :66-120

[8] Tractable conservative constraint satisfaction problems [J].

Bulatov, AA .

18TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2003, :321-330

[9] A simple algorithm for Mal'tsev constraints [J].

Bulatov, Andrei ;

Dalmau, Victor .

SIAM JOURNAL ON COMPUTING, 2006, 36 (01) :16-27

[10]

Burris S., 1981, COURSE UNIVERSAL ALG, DOI DOI 10.1007/978-1-4613-8130-3

← 1 2 3 →