Paper: Tractability and learnability arising from algebras with few subpowers (at LICS 2007)
Abstract
A k-edge operation \varphi on a finite set A is a k + 1-ary operation that satisfies the identities \begin{gathered} \varphi (x,x,y,...,y) \approx \varphi (x,y,x,y,...,y) \approx y, \hfill \\ \varphi (y,y,y,x,y,...,y) \approx \varphi (y,y,y,y,x,y,...,y) \approx ... \hfill \\ ... \approx \varphi (y,y,y,...,y,x) \approx y. \hfill \\ \end{gathered} We prove that any constraint language .. that, for some k \ge 1, has a k-edge operation as a polymorphism is globally tractable. We also show that the set of relations definable over .. using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries. Special instances of k-edge operations are Mal’cev and near-unanimity operations and so this class of constraint languages includes many well known examples.
BibTeX
@InProceedings{IdziakMarkovicMcKen-Tractabilityandlear, author = {Pawel Idziak and Petar Markovic and Ralph McKenzie and Matthew Valeriote and Ross Willard}, title = {Tractability and learnability arising from algebras with few subpowers}, booktitle = {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)}, year = {2007}, month = {July}, pages = {213--222}, location = {Wroclaw, Poland}, publisher = {IEEE Computer Society Press} }