Classi cation of Predicates and Languages
Rolf Wiehagen
FB Informatik, Uni. Kaiserslautern, P.O. Box 3049, 67653
Kaiserslautern, wiehagen@informatik.uni-kl.deCarl H. Smith
Department of Computer Science, University of Maryland, College
Park,MD 20912, smith@cs.umd.edu
Thomas Zeugmann
Inst. f. Theoretische Informatik, TH Darmstadt, 64283 Darmstadt,
zeugmann@iti.informatik.th-darmstadt.de

Abstract

We study the classi cation of recursive predicates and languages.
In particular, we compare the classi cation of predicates and languages with the classi cation of arbitrary recursive functions andwith learning. Moreover, we re ne our investigations by introducingclassi cation with a bounded number of mind changes and establish a new hierarchy. Furthermore, we introduce multi{classi cationand characterize it. Finally, we study the classi cation of families oflanguages that have attracted a lot of attention in learning theory.

1 Introduction
Learning and classi cation have attracted considerable attention by computer scientists, both in theory and practice. Inductive inference is an
important aspect of learning that has been widely studied (cf. Angluin
and Smith (1983, 1987)). The inductive inference problem is to take nitesamples of some target concept and to generalize an algorithm that can
produce all other samples of the same concept. Hence, inductive inference
may be regarded as the most general framework to study the generalization problem (cf. Michalski et al. (1983)). The classi cation problem may
be described as follows: Given a number of, usually nite, choices, one
takes nite samples of a target concept and has to nd out algorithmicallyto which of the possible choices the concept belongs to (cf. Duda and Hart
(1973)).
Recently, the problem of classi cation has been compared with the inductive inference problem in a recursion theoretic setting (cf. Wiehagen
12Classi cationand Smith (1992)). In that paper a new formalization of classi cation was
introduced. As it turned out, despite some obvious similarities, the two
notions are distinct and warrant further study.
The aim of the present paper is fourfold. First, we apply the previously developed formalism to investigate the classi cation of f0; 1g valued
recursive functions. These functions are often called predicates as they represent binary decisions on the input. By utilizing the isomorphism between
strings of symbols and the natural numbers, the predicates over the natural
numbers also represent formal languages. Hence, we simultaneously study
the classi cation of predicates and languages. On the one hand, we areinterested in learning the di erences and similarities between the classi cation of predicates and arbitrary recursive functions. On the other hand,
we enrich this study by considering the following two cases. In the rst
case we are satis ed if the classi cation algorithm produces any one of thepossibly many correct answers. In the second case we require the classi cation algorithm to produce all of the correct classi cations (cf. De nition
3). Second, we compare the power of classi cation algorithms that are allowed to produce only a single guess ( nite classi cation, cf. De nition 2,
the c = 0 case) with those that may change their mind a predetermined
xed number of times (cf. De nition 2, the c 2 IN case). Third, we introduce the notion of consistent classi cation (cf. De nition 4) and compare
it with general classi cation. Finally, we study classi cation of families oflanguages that have received considerable attention in learning theory.

2 Technical Preliminaries
By IN = f0; 1; 2; :::g we denote the set of all natural numbers. Members of
IN will serve as names for programs. The function computed by program
i will be denoted by 'i . Most reasonable ways of assigning names to programs results in a list '0 , '1 , : : : called an acceptable programming system(cf. Machtey and Young (1978)). By R we denote the class of all recursive functions. The class of f0; 1g valued recursive functions, our modelof both predicates and languages, is denoted by R0;1 . A set is recursively
enumerable (r.e.) i it is the domain of some 'i . Subset is denoted by and  denotes proper subset. For a function f 2 R and n 2 IN, let
f n = cod(f (0); f (1); :::; f (n)), where cod denotes a computable and bijective mapping from the set IN3 of all nite sequences of natural numbers
onto IN. Sometimes, for the sake of simplicity of notation, we identify
2 IN3 with cod( ), for a nite function.
Next, we formalize the modes of identi cation and classi cation mentioned in the introduction. As in Gold (1967) we de ne an inductive inference machine (abbr. IIM) to be an algorithmic device which works asfollows: The IIM takes as its input larger and larger initial segments of theRolf Wiehagen3graph of a function and it either requests the next function value, or it rst
outputs a hypothesis, i.e., a name of a program, and then it requests thenext function value.
A classi cation machine (abbr. CM) takes as input the graph of a function (as IIMs do) and it either requests the next function value, or it rst
outputs an integer chosen >from a nite set, and then it requests the next
function value.
Let M be an IIM or a CM. Furthermore, let i and j be two consecutive hypotheses produced by M . We say that M changes its mind, orsynonymously, M performs a mind change, i i 6= j . When dealing withmind changes, it is technically much more convenient to require the IIMs
to behave as follows. Let f be a recursive function. If M on f (0); :::; f (n)outputs its rst guess, then it has to output a hypothesis at any subsequent
step. It is easy to see that any IIM M may be straightforwardly converted^ behaving as required such that both machines produce theinto an IIM M
same sequence of mind changes.
We start with the formalization of learning. The following de nition isdue to Gold (1967) and Blum and Blum (1975).

De nition 1. Let U  R and let c 2 IN [ f3g. The class U is said to belearnable with at most c mind changes i there is an IIM M such that for
all f 2 U
(1) there is a j such that ' = f and M (f ) = j for almost all n 2 IN,(2) M , when successively fed with f (0); f (1); ::: performs at most c (c =3 means at most nitely many) mind changes, i.e., card(fn M (f ) 6=
M (f +1)g)  c.
n

j

n

n

If U can be learned by an IIM M with at most c mind changes, thenwe write U 2 EXc(M ). The class of all sets of recursive functions that arelearnable with at most c mind changes is denoted by EXc , an abbreviationfor explains as a program for f can be regarded as an explanation of theset of examples constituting the graph of f (cf. Case and Smith (1983)). If
U can be learned with 0 mind changes, then we also say that U is nitely
learnable. Moreover, we set F IN =df EX0 . If c = 3, then we usually omit
the lower index and simply say U can be learned.
Next, we formalize classi cation of nitely many sets.

De nition 2. Let S0; :::; S 01  R and let S = S0 [ ::: [ S 01 . Furthermore, let c 2 IN [ f3g. Then (S0 ; :::; S 01 ) is said to be classi able with at
most c mind changes i there is a CM M such that for all f 2 S(1) for all n 2 IN, whenever M, on input f , outputs a hypothesis j , thenj 2 f0; :::; k 0 1g,(2) there is a j such that f 2 S and M (f ) = j for almost all n 2 IN,
k

k

k

n

j

n

Classi cation

4(3) M , when successively fed f (0); f (1); ::: performs at most c (c = 3
means at most nitely many) mind changes, i.e., card(fn M (f n) 6=
M (f n+1 )g)  c.
If (S0 ; :::; Sk01 ) is classi ed by a CM with at most c mind changes, thenwe write (S0 ; :::; Sk01 ) 2 CLck (M ). By CLck we denote the collection of allk{tuples of sets that are classi able with at most c mind changes, i.e.,

CL = f(S0 ; :::; S 01 ) 9CM M [(S0; :::; S 01 ) 2 CL (M )]g:
c
k

k

S

c
k

k

Moreover, we set CLc =df k2 CLck . If c = 3, then we usually omit theupper index, and say simply that (S0 ; :::; Sk01 ) is classi able. Furthermore,
if c = 0, then we also say that (S0 ; :::; Sk01S) is nitely classi able, and set
F CLk =df CL0k . Finally, we set F CL =df k2 FCLk .
In the next de nition we consider the situation that the sets S0 ; :::; Sk01
are not necessarily disjoint. Looking at potential applications, it might behighly desirable not to obtain only one index of a set the target function
f belongs to, but the indices of all those sets that contain f . For example,
consider the case of automated medical diagnosis. In this case, we would
certainly desire to be aware of all the diseases that manifest the observed
symptoms. In our formalism, each disease is set Si and the functions to beclassi ed map symptoms to present or not present.

De nition 3. Let S0 ; :::; S 01  R, and let S = S0 [ ::: [ S 01 . Furthermore, let ALL = f0; :::; k 0 1g. Then (S0 ; :::; S 01 ) is said to be multi{
classi able i there is a CM M such that for all f 2 S(1) for all n 2 IN, whenever M, on input f , outputs a hypothesis HYP,
then HYP  ALL,(2) there is a non-empty set SUB  ALL such that(a) M (f ) = SUB for almost all n,(b) f 2 S for all j 2 SUB,(c) f 2= S for all m 2 ALLnSUB.
k

k

k

n

n

j

m

We write (S0 ; :::; Sk01 ) 2 Multi{CLk (M ) if (S0 ; :::; Sk01 ) is multi{classi ed by a CM M . By Multi{CLk we denote the collection
S of all k{tuples
of sets that are multi{classi able. We set Multi{CL =df k2 Multi{CLk .
Finally, we introduce consistent classi cation. The main intention is
as follows. Since potential users of a CM M never know whether M has
successfully nished its classi cation task, they might want to be sure thatthe hypotheses they receive do correctly re ect the information the CM
has been fed with.

De nition 4. Let S0 ; :::; S 01  R and let S = S0 [ ::: [ S 01 . Then
(S0 ; :::; S 01 ) is said to be consistently classi able i there is a CM M such
that
k

k

k

Rolf Wiehagen

5(1) (S0 ; :::; Sk01 ) 2 CLk (M ),(2) for all f 2 S , if M (f n ) = i, then there must be a function g 2 Sisuch that f and g coincide up to n.
We write (S0 ; :::; S 01 ) 2 Cons{CL (M ) if (S0 ; :::; S 01 ) is consistently
classi able by a CM M . By Cons{CL we denote the collection of allk{tuplesSof sets that are consistently classi able. Finally, we set Cons{CL =2 Cons{CL .
k

k

k

k

df

k

k

3 Classi cation of Predicates versus Classi cation of
Arbitrary Functions
In this section we compare the classi cation of f0; 1g valued functions withthe classi cation of functions in general. Looking at learning there areseveral results establishing major di erences between the learnability ofclasses of predicates and the inferability of arbitrary classes of recursivefunctions (cf. Blum and Blum (1975), Zeugmann (1983, 1988), Osherson,
Stob and Weinstein (1986)). Moreover, Freivalds, Kinber and Wiehagen(1992) discovered that consistent learning of predicates considerably di ers
from consistent identi cation of arbitrary recursive functions. Hence, it is
only natural to ask whether there are di erences between the classi cationof predicates and arbitrary recursive functions.
Clearly, if a collection of sets of f0; 1g valued functions is classi able,
then it is classi able as a collection of sets of arbitrary recursive functions.
To consider the converse direction, we need the following notation. Let
S  R; then we use (S ) to denote the restriction of S to predicates, i.e.,(S ) = S \ R0;1 .

Theorem 5. There is a collection of pairwise disjoint sets S0; S1 ; S2 suchthat(1) R = S0 [ S1 [ S2 ,(2) (S0 ; S1 ; S2 ) 2= CL,(3) ((S0 ); (S1 ); (S2 )) 2 CL23 .
The theorem has the following corollary.

Corollary 6. For any n  3 there is a collection of pairwise disjoint sets
exhausting R that is not in CL , but the collection of their restrictions topredicates is in CL .
nn

The latter results show that there might be interesting di erences between the classi cation of predicates and arbitrary functions. Later on, weshall point out some more di erences. In the next section we study thepower of classi cation algorithms with respect to the allowed number ofmind changes.

Classi cation

6

4 Finite Classi cation versus Classi cation and Learnability
Our next theorem in particular states that even the classi cation of two
sets might be too complex to be done by a nitely working CM.

Theorem 7. For any k > 1 there are pairwise disjoint sets S0; 1 1 1 ; S 01
such that(1) S0 [ S1 [ 1 1 1 [ S 01 = R0 1 ,(2) (S0 ; S1 ; 1 1 1 ; S 01 ) 2 CL n FCL.
k

k

;

k

In contrast to Theorem 7, it is possible to split R0;1 into disjoint, nitely
classi able sets.

Theorem 8. For any k > 1 there are pairwise disjoint sets S0; 1 1 1 ; S 01
such that(1) S0 [ S1 [ 1 1 1 [ S 01 = R0 1 ,(2) (S0 ; S1 ; 1 1 1 ; S 01 ) 2 F CL.
k

k

;

k

Next we compare nite classi cation and learnability. If a classi cation
machine outputs a hypothesis i, then we know almost all about the corresponding set Si, since there are only nitely many sets S0 ; :::; Sk01 . On theother hand, if an IIM outputs a hypothesis i, then we know almost nothing
about the corresponding function 'i. Hence, at rst glance it seems mucheasier to disprove a CM than to fool an IIM. However, the situation is much
more subtle, as the following theorems show.

Theorem 9. For any S0  R0 1 with S0 2 F IN , there is a S1 such that
(1) S1  R0 1 ,(2) S1 2 F IN ,(3) S0 \ S1 = ;,(4) (S0 ; S1 ) 2 F CL.
;;

The latter theorem allows the following interpretation. Any \easily"learnable class can be completed to an \easily" classi able pair. Thus,
sometimes learning and classi cation are not very distinct. On the other
hand, we have the following:

Theorem 10. For any S0  R0 1 with S0 2 F IN , there is a S1 such that
(1) S1  R0 1 ,(2) S1 2= EX ,(3) S0 \ S1 = ;,(4) (S0 ; S1 ) 2 F CL.
;;

Rolf Wiehagen

7

5 Bounding the Number of Mind Changes
For nite classi cation (F CL) a CM is not allowed to change its conjecture
at all. For standard classi cation (CL) a CM is allowed to change its
conjecture an arbitrary nite number of times. The precise number of mindchanges has not to be determined in advance. In the study of inductive
inference, a mind change hierarchy was discovered by xing in advancea particular number of mind changes that an IIM was allowed to make(cf. Case and Smith (1983)). In the sequel we present a hierarchy forclassi cation based on a xed number of allowed mind changes.

Theorem 11. For any k there are sets S0, S1 , 1 1 1, S +1 such that
(1) S0 [ S1 [ 1 1 1 [ S +1 = R0 1 ,kk(2) (S0 ; 1 1 1 ; Sk+1) 2 CL

;

k +1

n CL .
kMoreover, it is also possible to prove a hierarchy in the number of mindchanges that is not related to the number of sets to be classi ed.

Theorem 12. For any c 2 IN there exist pairwise disjoint sets S0 ; S1 
R0 1 such that (S0 ; S1) 2 CL2+1 n CL2 .
;cc

6 Classi cation versus Multi{Classi cation and Consistent Classi cation
In this section we compare the power of classi cation, multi{classi cationand consistent classi cation. In particular, we are interested in learningwhether or not multi{classi cation or consistent classi cation is harder toachieve than ordinary one. Since neither multi{classi cation nor consistentclassi cation has been studied in the framework present here, our goal is
twofold. First we are interested in general results concerning the classi cation power of these classi cation modes. Second, we ask whether or not
the results obtained do extend to the classi cation of predicates.
Our next theorem compares multi{classi cation and ordinary classi cation in the nite case.

Theorem 13. Multi{F CL2  F CL2
Next we aim to characterize multi{classi cation in terms of standard
classi cation. For that purpose, we introduce the notion of a mosaic.
Let S0 ; :::; Sk01  R and S = S0 [T ::: [ Sk01. SLet ALL = f0; :::; k 0 1g
and SUB  ALL. Then let SSUB = j2SUB Sj n i2 ALLnSUB Si . Clearly,
SSUB is the set of all f 2 S that belong to any of the classes Sj , j 2 SUB,

Classi cation

8

and to none of the classes Si , i 2 ALLnSUB. Let mosaic(S0 ; :::; Sk01 ) be
the tuple of all sets SSUB , where SUB  ALL.
Obviously, mosaic(S0 ; :::; Sk01 ) is a 2k {tuple of pairwise disjoint sets
the union of which is S . Note that some components of mosaic(S0 ; :::Sk01 )may be empty.
Finally, let mosaic(S0 ; :::; Sk01 ) = (T0 ; :::; T2k 01 ). Moreover, without
loss of generality we assume that the Tj 's, 0  j  2k 0 1, are orderedin such a way that from the index j the corresponding set SUB can becomputed such that SS U B = Tj and vice versa. Formally, this can berealized by a one-to-one mapping m from the set of all subsets SUB of ALL
onto the set f0; :::2k 0 1g such that for any SUB  ALL, SSU B = Tm(SU B ) .
We have obtained the following characterization.

Theorem 14. For all k  2 and all sets S0 ; :::; Sk01  R we have:(S0 ; :::; Sk01 ) 2 Multi{CL if and only if mosaic(S0 ; :::; Sk01 ) 2 CL.
Finally in this section we relate consistent classi cation to ordinary one.

Theorem 15.

Cons{CL  CL

Note that all theorems in this section remain valid if one considers
exclusively the classi cation of predicates.

7 Classi cation of Languages
In this section rst we examine the classi cation of the regular languages(cf. Lewis and Papadimitriou (1981)). The regular languages can be modeled as predicates as well. This is done by xing an isomorphism between
strings over the alphabet of the regular language and the natural numbers. Then a (regular) language represented by a f0; 1g valued function
f is the set of strings that correspond to the natural numbers in the set
fx f (x) = 1g. The details of this encoding will be suppressed as muchas possible without sacri cing clarity. By a positive example we mean astring that corresponds to a value x such that f (x) = 1. Similarly, by anegative example we mean a string that corresponds to a value x such thatf (x) = 0.

Theorem 16. It is impossible to classify an arbitrary language as being
either regular or not regular.
By way of contrast with Theorem 16, it is possible to separate arbitrarily
large subsets of the regular languages >from the rest.

Rolf Wiehagen

9

Theorem 17. Let n be an arbitrary natural number. Let S0 be the set of
all regular languages that are recognized by some n-state nite automaton.
Let S1 be all the languages not in S0 . Then (S0; S1 ) 2 CL.
The last theorem relates the learnability of indexed families of languages
to their classi ability. In particular, the next theorem establishes a condition under what circumstances a classi cation algorithm can be derived
from a given learning algorithm. In general, it is impossible to convert alearning algorithm into a classi cation machine, as previously obtained results show (cf. Wiehagen and Smith (1992)). Due to lack of space, we canonly sketch the next result. L = (Lj )j 2IN is said to be an indexed family, if
all languages Lj are non{empty, and there is an algorithm that uniformly
decides membership in Lj for all strings over the underlying alphabet andall j 2 IN. The inferability of indexed families has attracted a lot of attention in learning theory (cf. Lange and Zeugmann (1993) and the references
therein). Of particular interest is the learnability of indexed families frompositive data. We have obtained the following theorem.

Theorem 18. Let m  1 and let L be any indexed family over somexed alphabet that can be learned from positive data with at most m mindchanges. Then there exists a partition of L into m + 1 pairwise disjointclasses L0; :::; L such that
(1) L0 [ ::: [ L = L,mm(2) (L0 ; :::; Lm ) 2 CLm+1 .

Finally, all proofs of the theorems stated above can be found in Wiehagen, Smith and Zeugmann (1993).

Acknowledgment

The rst author was supported by the German Ministry for Research
and Technology (BMFT) under grant no. 01 IW 101. The second author
was supported in part by NSF Grant 9020079.

8 References
1. Angluin, D., and Smith, C.H. (1983). Inductive inference: theory andmethods, Computing Surveys 15, 237 - 269.
2. Angluin, D., and Smith, C.H. (1987). Formal inductive inference, in\Encyclopedia of Arti cial Intelligence" (St.C. Shapiro, Ed.), Vol. 1,
pp. 409 - 418, Wiley-Interscience Publication, New York.
3. Blum, L., and Blum, M. (1975). Toward a mathematical theory of
inductive inference, Information and Control 28, 122 - 155.

10Classi cation

4. Case, J., and Smith, C.H. (1983). Comparison of identi cation criteria
for machine inductive inference, Theoretical Computer Science 25,
193 - 220.
5. Duda, R., and Hart, P. (1973). Pattern Classi cation and Scene Analysis, Wiley Interscience.
6. Freivalds, R., Kinber, E.B., and Wiehagen, R. (1992). Convergently versus divergently incorrect hypotheses in inductive inference, GOSLER
Report 05/92, January 1992, Fachbereich Mathematik und Informatik, TH Leipzig.
7. Freivalds, R.V., and Wiehagen, R. (1979). Inductive inference with additional information, Journal of Information Processing and Cybernetics (EIK) 15, 179 - 184.
8. Gold, M.E. (1967). Language identi cation in the limit, Information
and Control 10, 447 - 474.
9. Jantke, K.P., and Beick, H.R. (1981). Combining postulates of naturalness in inductive inference, Journal of Information Processing andCybernetics (EIK) 17, 465 - 484.
10. Lange, S., and Zeugmann, T. (1993). Learning recursive languages
with bounded mind changes, International Journal of Foundationsof Computer Science, 4, Vol. 2, 157 - 178.
11. Lewis, H., and Papadimitriou, C. (1981). Elements of the Theory ofComputation, Prentice-Hall, Inc., Englewood Cli s, New Jersey.
12. Machtey, M., und Young, P. (1978). An Introduction to the General
Theory of Algorithms, North-Holland, New York.
13. Michalski, R.S., Carbonell, J.G., and Mitchell, T.M. (1983). Machine
Learning, Tioga Publishing Co., Palo Alto, CA.
14. Osherson, D., Stob, M., and Weinstein, S. (1986). Systems that Learn,

An Introduction to Learning Theory for Cognitive and Computer Scientists, MIT-Press, Cambridge, Massachusetts.

15. Wiehagen, R., and Smith, C. (1992). Classi cation versus generalization, in \Proceedings 5th Annual ACM Workshop on Computational
Learning Theory," Pittsburgh, July 1992, pp. 224 - 230, ACM Press,
New York.
16. Wiehagen, R., Smith, C, and Zeugmann, T. (1993). Classifying recursive predicates and languages, GOSLER Report 21/93, Dezember
1993, Fachbereich Mathematik und Informatik, TH Leipzig.
17. Zeugmann, T. (1983). A-posteriori characterizations in inductive inference of recursive functions, Journal of Information Processing andCybernetics (EIK) 19, 559 - 594.
18. Zeugmann, T. (1988). On the power of recursive optimizers, Theoretical Computer Science 62, 289 - 310.