GRAMMATICAL COMPLEXITY AND INFERENCE

Abstract

The problem of inferring a grammar for a set of symbol strings is considered and a number of new decidability results obtained. Several notions of grammatical complexity and their properties are studied. The question of learning the least complex grammar for a set of strings is investigated leading to a variety of positive and negative results. This work is part of a continuing effort to study the problems of representation and generalization through the grammatical inference question.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1969
Accession Number
AD0692390

Entities

People

  • James Gips
  • James J. Horning
  • Jerome A. Feldman
  • Stephen Reder

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Bayes Theorem
  • Channel Capacity
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Grammars
  • Information Theory
  • Language
  • New York
  • Notation
  • Pattern Recognition
  • Probability
  • Probability Distributions
  • Random Variables

Readers

  • Mathematical Modeling and Probability Theory.
  • Neural Network Machine Learning.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms
  • AI & ML - Machine Translation