# ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

# Logic in Computer Science (LICS 2007)

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