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

Abstract

It is shown that (1) there exists a language L sub 0 which is generated by a linear grammar and is not T(n)-recognizable by any on-line multi-tape Turing machine if lim T(n)/(n/logn) 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)

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1966
Accession Number
AD0632569

Entities

People

  • Tadao Kasami

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Automata
  • Circuits
  • Computational Complexity
  • Grammars
  • Language
  • Linguistics
  • Machines
  • Recognition
  • Sequences
  • Switching
  • Switching Circuits

Readers

  • Mathematical Modeling and Probability Theory.