Wednesday, August 30, 2006; 9am Sc S105C

Speaker: James Farrell, Candidate, M.S. in Computer Science

We propose and define a minimal cooperative problem that demonstrates key features of cooperative behavior, and allows for detailed study of the acquisition and mechanism of such behavior. This problem is characterized as a task of language generation by cooperating grammars. We present results for the induction of regular and context-free languages by pairs of right-linear grammars using grammar-based genetic programming. Populations of cooperating grammar systems, we found, were able to induce regular languages more quickly and accurately than a non-cooperative single-component control. The system was also able, in some cases, to learn context-free languages, despite the formal inability of single regular components to produce this class of languages.