Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/28522
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Idziak Paweł | - |
dc.contributor.author | Marković Petar | - |
dc.contributor.author | McKenzie Ralph | - |
dc.contributor.author | Valeriote Matthew | - |
dc.contributor.author | Willard Ross | - |
dc.date.accessioned | 2020-12-14T15:29:20Z | - |
dc.date.available | 2020-12-14T15:29:20Z | - |
dc.date.issued | 2007 | - |
dc.identifier.isbn | 0-7695-2908-9 | - |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/28522 | - |
dc.description.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. | en |
dc.language.iso | en | - |
dc.relation.ispartof | 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 | en |
dc.source | CRIS UNS | - |
dc.source.uri | http://cris.uns.ac.rs | - |
dc.title | Tractability and learnability arising from algebras with few subpowers | en |
dc.type | Conference Paper | en |
dc.identifier.doi | 10.1109/LICS.2007.50 | - |
dc.identifier.url | https://www.cris.uns.ac.rs/record.jsf?recordId=84119&source=BEOPEN&language=en | en |
dc.relation.lastpage | 224 | - |
dc.relation.firstpage | 213 | - |
dc.identifier.externalcrisreference | (BISIS)84119 | - |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
Appears in Collections: | PMF Publikacije/Publications |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.