Learning intersection-closed classes with signatures

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Bulatov, Andrei A.
• dc.contributor.author Chen, Hubie
• dc.contributor.author Dalmau, Víctor
• dc.date.accessioned 2019-01-18T09:09:25Z
• dc.date.available 2019-01-18T09:09:25Z
• dc.date.issued 2007
• dc.description.abstract Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. We give a learning algorithm in the exact model with equivalence queries for such classes. This algorithm utilizes a novel encoding scheme, which we call a signature.en
• dc.description.sponsorship The first author was supported by an NSERC Discovery Grant. The second and third authors were supported by grant TIC 2002-04470-C03 and the EU PASCAL Network of Excellence IST-2002-506778. The third author was also supported by the MEC under the program “Ramon y Cajal”, grant TIC 2002-04019-C03, and MODNET Marie Curie Research Training Network MRTN-CT-2004-512234.
• dc.format.mimetype application/pdf
• dc.identifier.citation Bulatov A, Chen H, Dalmau V. Learning intersection-closed classes with signatures. Theor Comput Sci. 2007 Sep 6;382(3):209-20. DOI: 10.1016/j.tcs.2007.03.039
• dc.identifier.doi http://dx.doi.org/10.1016/j.tcs.2007.03.039
• dc.identifier.issn 0304-3975
• dc.identifier.uri http://hdl.handle.net/10230/36326
• dc.language.iso eng
• dc.publisher Elsevier
• dc.relation.ispartof Theoretical Computer Science. 2007 Sep 6;382(3):209-20.
• dc.relation.projectID info:eu-repo/grantAgreement/ES/1PN/TIC2002-04470-C03
• dc.relation.projectID info:eu-repo/grantAgreement/EC/FP7/506778
• dc.relation.projectID info:eu-repo/grantAgreement/EC/FP6/512234
• dc.relation.projectID info:eu-repo/grantAgreement/ES/1PN/TIC2002-04019-C03-03
• dc.rights © Elsevier http://dx.doi.org/10.1016/j.tcs.2007.03.039
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Computational learning
• dc.subject.keyword Closure algorithm
• dc.subject.keyword Polymorphism
• dc.subject.keyword Quantified formulas
• dc.title Learning intersection-closed classes with signatures
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/acceptedVersion