Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке:
https://open.uns.ac.rs/handle/123456789/28522
Назив: | Tractability and learnability arising from algebras with few subpowers | Аутори: | Idziak Paweł Marković Petar McKenzie Ralph Valeriote Matthew Willard Ross |
Датум издавања: | 2007 | Часопис: | 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 | Сажетак: | 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 |
Налази се у колекцијама: | PMF Publikacije/Publications |
Приказати целокупан запис ставки
Преглед/и станица
2
Протекла недеља
1
1
Протекли месец
0
0
проверено 10.05.2024.
Google ScholarTM
Проверите
Алт метрика
Ставке на DSpace-у су заштићене ауторским правима, са свим правима задржаним, осим ако није другачије назначено.