Computer Science
Computer Science
bullet Gourds will fly: Rowan University American Society of Mechanical Engineers to host fifth annual Pumpkin Chunkin’ | More

bullet Hail to the Profs! Homecoming 2014 in pictures | More

bullet Second biennial ScholarFest to celebrate Rowan research | More

bullet Rowan hosts talk on “Controlling Ebola Virus Outbreaks: A New Strategy to Block Virus Transmission and Spread” | More

bullet Prof pride: Alumni flock to campus for Homecoming | More

Technical Report Number TR1996-1

Title
Synthesizing Enumeration Techniques for Language Learning

Authors
Ganesh Baliga
Department of Computer Science
Rowan College of New Jersey
Glassboro, NJ 08028

John Case
Department of Computer and Information Sciences
University of Delaware
Newark, DE 19716

Sanjay Jain
Information Systems and Computer Science department
National University of Singapore
Singapore

Abstract

In the context of learning programs in the limit for functions, a variety of enumeration techniques are important and ubiquitous. Here is the archetypal case. Suppose one has an recursively enumerable set
of programs for computing total functions. One proceeds as follows. At each point one is given finitely much data about an input function, one conjectures the first program, if any, listed in P that is correct on that data. Clearly for functions f computed by some program in P, this procedure will eventually lock onto a fixed conjecture correct for f. We consider the same technique as might be applied to language learning.

The present paper was inspired by the following amazingly negative result due to Osherson, Stob and Weinstein. They show: there is no algorithm for translating any pair of grammars (g,g') into a learning procedure which, from positive data about any one of the languages generated by g and g', finds in the limit, for this language, a correct grammar! In this paper we seek to assuage this negative result by loosening the requirements of successful learning. We consider the limiting synthesis of learning machines for learnable recursively enumerable classes of languages. One of the results in this paper is a
characterization of uniformly decidable classes in terms of some conditions due to Dana Angluin.