Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/28520
Nаziv: | Tractability and Learnability Arising from Algebras with Few Subpowers | Аutоri: | Idziak Paweł Marković Petar McKenzie Ralph Valeriote Matthew Willard Ross |
Ključnе rеči: | constraint satisfactionlearnabilitycomplexitypolymorphismMal'cevnear-unanimitypolynomially expressivefew subpowers | Dаtum izdаvаnjа: | 2010 | Čаsоpis: | SIAM Journal on Computing / Society for Industrial and Applied Mathematics | Sažetak: | 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 |
Nаlаzi sе u kоlеkciјаmа: | PMF Publikacije/Publications |
Prikаzаti cеlоkupаn zаpis stаvki
Prеglеd/i stаnicа
12
Prоtеklа nеdеljа
1
1
Prоtеkli mеsеc
0
0
prоvеrеnо 10.05.2024.
Google ScholarTM
Prоvеritе
Аlt mеtrikа
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.