Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/28522
Title: | Tractability and learnability arising from algebras with few subpowers | Authors: | Idziak Paweł Marković Petar McKenzie Ralph Valeriote Matthew Willard Ross |
Issue Date: | 2007 | Journal: | Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, 2007., Twenty-Second Annual IEEE Symposium on Logic in Computer Science - LICS '07, Wroclaw, Poland, 2007 | Abstract: | A k-edge operation phi on a finite set A is a k + 1-ary operation that satisfies the identities phi (x,x,y,...,y) ap phi(x,y,x,y,...,y) ap y, phi(y,y,y,x,y,...,y) ap phi(y,y,y,y,x,y,...,y) ap ... ap ... phi(y,y,y,...,y,x) ap y. We prove that any constraint language .. 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 Gamma 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. | URI: | https://open.uns.ac.rs/handle/123456789/28522 | ISBN: | 0-7695-2908-9 | DOI: | 10.1109/LICS.2007.50 |
Appears in Collections: | PMF Publikacije/Publications |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.