Learning expressions and programs over monoids

• Published in: Information and computation 2006-02, Vol.204 (2), p.177-209
• Main Authors: Gavaldà, Ricard, Tesson, Pascal, Thérien, Denis
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Artificial intelligence; Computer science; control theory; systems; Exact sciences and technology; Learning and adaptive systems; Theoretical computing
• ISSN: 0890-5401; 1090-2651
• DOI: 10.1016/j.ic.2005.09.003

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 focus on monoids which are either groups or aperiodic, and on the learning model of exact learning from queries. For a group G, we prove that expressions over G are efficiently learnable if G is nilpotent, and impossible to learn efficiently (under cryptographic assumptions) if G is nonsolvable. We present some results for restricted classes of solvable groups, and point out a connection between their efficient learnability and the existence of lower bounds on their computational power in the program model. For aperiodic monoids, our results seem to indicate that the monoid class known as DA captures exactly learnability of expressions by polynomially many Evaluation queries. When using programs instead of expressions, we show that our results for groups remain true, while the situation is quite different for aperiodic monoids.