Learning Restricted Classes of Regular Languages Using Loop Induction.

Recent negative results on learning Deterministic Finite Automata (DFAs) have encouraged researchers to investigate alternative models of learning in which more information is available to the learner; however, the complementary approach of considering the learnability of restricted classes of DFAs has received little attention. This paper looks at the problem of learning restricted classes of DFAs under a restricted model of DFA learning called loop induction. Loop induction is a formal model of the problem of learning iterative macro-operators. In loop induction, only positive examples are available, and a certain type of incremental processing of the examples is enforced.