Horning, J. J.

A study of grammatical inference


Abstract: Grammatical inference is an inductive process of discovering an acceptable grammar for a language, on the basis of finite samples from the language. The study has the goals of devising useful inference procedures and of demonstrating a sound formal basis for such procedures. It states the general grammatical inference problem for formal languages, reviews previous work, establishes definitions and notation, and states a position on evaluation measures. It indicates a solution for a particular class of grammatical inference problems, based on an assumed probabilistic structure.