Classifying Recursive Predicates and Languages

Authors: Rolf Wiehagen, Carl Smith and Thomas Zeugmann

Source: “Algorithmic Learning for Knowledge-Based Systems,” (K.P. Jantke and S. Lange, Eds.), Lecture Notes in Artificial Intelligence 961, pp. 174 - 189, Springer-Verlag 1995.

Abstract.

Our goal is to arrive at a deeper understanding of the classification problem. We study a particular collection of classification problems, the classification of recursive predicates and languages. In particular, we compare the classification of predicates and languages with the classification of arbitrary recursive functions and with learning. We refine our investigations by introducing classification within a resource bound and establish a new hierarchy. We introduce a formalization of multi-classification and characterize it. We also introduce consistent classification and compare it with standard classification. Finally, we study the classification of families of languages that have attracted attention in learning theory.