Learning indexed families of recursive languages from positive data: A survey

Authors: Steffen Lange, Thomas Zeugmann, and Sandra Zilles

Source: Theoretical Computer Science, Vol. 397, Issues 1-3, 2008, 194-232.
(Special Issue Forty Years of Inductive Inference: Dedicated to the 60th Birthday of Rolf Wiehagen)

Abstract. In the past 40 years, research on inductive inference has developed along different lines, e.g., in the formalizations used, and in the classes of target concepts considered. One common root of many of these formalizations 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 focuses on 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 interest because of their naturalness. 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, and artificial intelligence in general.


Keywords: Inductive inference; Formal languages; Recursion theory; Query learning


©Copyright 2008, Elsevier Science B.V.