Accession Number : AD0688147

Title :   GRAMMARS WITH TIME FUNCTIONS,

Corporate Author : HARVARD UNIV CAMBRIDGE MASS COMPUTATION LAB

Personal Author(s) : Book,Ronald V.

Report Date : FEB 1969

Pagination or Media Count : 135

Abstract : The subject of this paper is the study of formal grammars and of formal languages from the viewpoint of time-bounded grammars. The principal results focus on properties similar to those of families of languages defined by time-bounded nondeterministic Turing machines. Chapter 1 contains an overview of the results of this paper and a summary of basic ideas of automata theory and mathematical linguistics used here. In Chapter 2, basic properties of time-bounded grammars and languages generated by time-bounded grammars are investigated. Chapter 3 establishes the positive closure and containment properties of families of languages defined by grammars whose time functions are bounded by bounding functions. Nonclosure, undecidability, and hierarchy results are established in Chapter 4. (Author)

Descriptors :   (*COMPUTATIONAL LINGUISTICS, AUTOMATA), MACHINE TRANSLATION, PROGRAMMING LANGUAGES, GROUPS(MATHEMATICS), RECURSIVE FUNCTIONS, SET THEORY, GRAMMARS, SIMULATION, THEOREMS

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE