Paper: Tractability and learnability arising from algebras with few subpowers (at LICS 2007)

Authors: Pawel Idziak Petar Markovic Ralph McKenzie Matthew Valeriote Ross Willard

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}
  }