Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке:
https://open.uns.ac.rs/handle/123456789/28520
Назив: | Tractability and Learnability Arising from Algebras with Few Subpowers | Аутори: | Idziak Paweł Marković Petar McKenzie Ralph Valeriote Matthew Willard Ross |
Кључне речи: | constraint satisfactionlearnabilitycomplexitypolymorphismMal'cevnear-unanimitypolynomially expressivefew subpowers | Датум издавања: | 2010 | Часопис: | SIAM Journal on Computing / Society for Industrial and Applied Mathematics | Сажетак: | A constraint language $\Gamma$ on a finite set A has been called polynomially expressive if the number of n-ary relations expressible by $\exists\wedge$-atomic formulas over $\Gamma$ is bounded by $\exp(O(n^k))$ for some constant k. It has recently been discovered that this property is characterized by the existence of a $(k+1)$-ary polymorphism satisfying certain identities; such polymorphisms are called k-edge operations and include Mal'cev and near-unanimity operations as special cases. We prove that if $\Gamma$ is any constraint language which, for some $k>1$, has a k-edge operation as a polymorphism, then the constraint satisfaction problem for $\langle\Gamma\rangle$ (the closure of $\Gamma$ under $\exists\wedge$-atomic expressibility) 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. | URI: | https://open.uns.ac.rs/handle/123456789/28520 | ISSN: | 0097-5397 | DOI: | 10.1137/090775646 |
Налази се у колекцијама: | PMF Publikacije/Publications |
Приказати целокупан запис ставки
Преглед/и станица
12
Протекла недеља
1
1
Протекли месец
0
0
проверено 10.05.2024.
Google ScholarTM
Проверите
Алт метрика
Ставке на DSpace-у су заштићене ауторским правима, са свим правима задржаним, осим ако није другачије назначено.