TCS-TR-A-07-31Date: Tue Oct 30 21:46:32 2007 Title: Learning Indexed Families of Recursive Languages from Positive Data Authors: Steffen Lange, Thomas Zeugmann and Sandra Zilles Contact:
Abstract. In the past 40 years, research on inductive inference has developed along different lines, concerning different formalizations of learning models and in particular of target concepts for learning. One common root of many of these is Gold's model of identification in the limit. This model has been studied for learning recursive functions, recursively enumerable languages, and recursive languages, reflecting different aspects of machine learning, artificial intelligence, complexity theory, and recursion theory. One line of research in this context focuses on so-called indexed families of recursive languages—classes of recursive languages described in a representation scheme for which the question of membership for any string in any of the given languages is effectively decidable with a uniform procedure. Such language classes are of high relevance, since their naturalness makes them interesting for many applications. The survey at hand picks out important studies on learning indexed families (including basic as well as recent research), summarizes and illustrates the corresponding results, and points out links to related fields such as grammatical inference, machine learning, or artificial intelligence in general. ©Copyright 2007 Authors |