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/28522
Nаziv: | Tractability and learnability arising from algebras with few subpowers | Аutоri: | Idziak Paweł Marković Petar McKenzie Ralph Valeriote Matthew Willard Ross |
Dаtum izdаvаnjа: | 2007 | Čаsоpis: | 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 | Sažetak: | 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 |
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а
2
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.