THE UNSOLVABILITY OF THE RECOGNITION OF LINEAR CONTEXT-FREE LANGUAGES.

Abstract

The problem of whether a given context-free language is linear is shown to be recursively undecidable. (Author)

Document Details

Document Type
Technical Report
Publication Date
Aug 18, 1965
Accession Number
AD0628202

Entities

People

  • Shelia A. Greibach

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Behavior And Behavior Mechanisms
  • Behavioral Disciplines And Activities
  • Behavioral Sciences
  • Cooperation
  • Group Dynamics
  • Identification
  • Language
  • Recognition