Grammars with Time Functions

Front Cover
Harvard University, 1969 - Formal languages - 135 pages
0 Reviews
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).

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.


First Principles
Positive Closure and Containment Properties
Negative Closure Properties and Hierarchy Results

2 other sections not shown

Common terms and phrases

Bibliographic information