22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007) Tractability and learnability arising from algebras with few subpowers Wroclaw, Poland July 10-July 14 ISBN: 0-7695-2908-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2007.50
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.
Citation:
Pawel Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, Ross Willard, "Tractability and learnability arising from algebras with few subpowers," lics, pp.213-224, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), 2007 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb