**ERIC Number:**ED342665

**Record Type:**Non-Journal

**Publication Date:**1990-Jul

**Pages:**147

**Abstractor:**N/A

**Reference Count:**N/A

**ISBN:**N/A

**ISSN:**N/A

Topics in Computational Learning Theory and Graph Algorithms.

Board, Raymond Acton

This thesis addresses problems from two areas of theoretical computer science. The first area is that of computational learning theory, which is the study of the phenomenon of concept learning using formal mathematical models. The goal of computational learning theory is to investigate learning in a rigorous manner through the use of techniques from theoretical computer science. Much of the work in this field is in the context of "probably approximately correct" (PAC) model of learning, which is carried out in a probabilistic environment. Of particular interest are the questions of determining for which classes of concepts the PAC-learning problem is tractable and discovering efficient learning algorithms for such classes. The second area from which topics are drawn is that of online algorithms for graph-theoretic problems. Many problems in such fields as communications, transportation, scheduling, and networking can be reduced to that of finding a good graph algorithm. After an introduction in Chapter 1, some background information is provided in Chapter 2 on the field of computational learning theory. In Chapter 3 it is shown that for any concept class having a particular closure property, the existence of a graph algorithm implies that the class is PAC-learnable. Chapter 4 defines a variation on the standard PAC model of learning called semi-supervised learning, a model which permits the rigorous study of learning situations where the teacher plays only a limited role. Chapter 5 deals with the problem of prediction as performed by deterministic finite automata, counter machines, and deterministic pushdown automata. Chapter 6 investigates the power and the performance of online algorithms for a certain class of graph problems, referred to as vertex labeling problems. (77 references) (JJK)

**Publication Type:**Dissertations/Theses - Doctoral Dissertations

**Education Level:**N/A

**Audience:**N/A

**Language:**English

**Sponsor:**National Science Foundation, Washington, DC.

**Authoring Institution:**Illinois Univ., Urbana. Dept. of Computer Science.