Classification of Predicates and Languages

Authors: Rolf Wiehagen, Carl H. Smith and Thomas Zeugmann

Source: ``Proc. 1st EURO-COLT'93 - Computational Learning Theory,'' 20th - 22nd December, 1993, University of London, The Institute of Mathematics and its Applications Conference Series, New Series Number 53, pp. 171 - 181, Oxford University Press, Oxford 1994.

Abstract. We study 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. Moreover, we refine our investigations by introducing classification with a bounded number of mind changes and establish a new hierarchy. Furthermore, we introduce multi-classification and characterize it. Finally, we study the classification of families of languages that have attracted a lot of attention in learning theory.