Learning expressions and programs over monoids

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/97847

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Gavaldà Mestre, Ricard
dc.contributor.author	Tesson, Pascal
dc.contributor.author	Thérien, Denis
dc.date	2001-09
dc.identifier.citation	Gavaldà, R., Tesson, P., Thérien, D. "Learning expressions and programs over monoids". 2001.
dc.identifier.uri	http://hdl.handle.net/2117/97847
dc.language.iso	eng
dc.relation	LSI-01-38-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica
dc.subject	Monoids
dc.subject	Computational complexity
dc.subject	Expressions learning
dc.subject	Programs learning
dc.title	Learning expressions and programs over monoids
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	We study the problem of learning an unknown function represented as an expression or a program over a known finite monoid. As in other areas of computational complexity where programs over algebras have been used, the goal is to relate the computational complexity of the learning problem with the algebraic complexity of the finite monoid. Indeed, our results indicate a close connection between both kinds of complexity. We present results for Abelian, nilpotent, solvable, and nonsolvable groups, as well as for some important subclasses of aperiodic monoids.