Accession Number:

AD0632569

Title:

A NOTE ON COMPUTING TIME FOR RECOGNITION OF LANGUAGES GENERATED BY LINEAR GRAMMARS,

Descriptive Note:

Corporate Author:

ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s):

Report Date:

1966-04-01

Pagination or Media Count:

13.0

Abstract:

It is shown that 1 there exists a language L sub 0 which is generated by a linear grammar and is not Tn-recognizable by any on-line multi-tape Turing machine if lim Tnnlogn squared as n approaches infinity equals zero and 2 any language generated by a linear grammar is n squared-recognizable by an on-line single-tape Turing machine in the sense of Hartmanis and Stearns Computational complexity of recursive sequences, Proc. the Fifth Annual Symp. of Switching Circuit Theory and Logical Design, p. 82-90 1964. Author

Subject Categories:

  • Linguistics
  • Computer Hardware
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE