Seminar on Computational Learning and Adaptation

  Learning DFA from Simple Examples

Rajesh Parekh
Business Intelligence Group
Blue Martini Software

Efficient learning of DFA is a challenging research problem in grammatical inference. It is known that both exact and approximate (in the PAC sense) identifiability of DFA is hard. Pitt has posed the following open research problem: Are DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution?. I will discuss the learnability under the Solomonoff-Levin universal distribution (m) of the class of DFA whose canonical representations have logarithmic Kolmogorov complexity. I will show that the class of DFA is efficiently learnable under the PACS (PAC learning with simple examples) model wherein positive and negative examples are sampled according to the universal distribution conditional on a description of the target concept. Further, I will address the relationship between models for learning in helpful environments and explain how unnatural collusion between the teacher and learner can potentially trivialize the task of learning in such environments.

This is joint work with Vasant Honavar, Department of Computer Science, Iowa State University.

Return to the seminar schedule