Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1993-01-01

Filename

WUCS-93-2.PDF

DOI:

10.7936/K7028PR3

Technical Report Number

WUCS-93-2

Abstract

We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible. Not surprisingly, such a model remedies the non-intuitive aspects of otehr models in which the teacher must successfully teach any consistent learner. We prove that any class that can be exactly identified by a deterministic polynomial-time algorithm with access to a very rich set of example-based queries is teachable by a computationally unbounded teacher and a polynomial-time learner. In addition, we present other general results relating this model of teaching to various previous results. We also consider the problem of designing teacher/learner pairs in which both the teacher and learner are polynomial-time algorithms and describe teacher/learner pairs for the classes of 1-decision lists and Horn sentences.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7028PR3

Download

Share

COinS