Accession Number : AD0632569

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

Corporate Author : ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s) : Kasami,Tadao

Report Date : APR 1966

Pagination or Media Count : 13

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)

Descriptors :   (*COMPUTATIONAL LINGUISTICS, TIME), COMPUTERS, AUTOMATA, GRAMMARS, LINEAR SYSTEMS, MAGNETIC TAPE

Subject Categories : Linguistics
      Computer Hardware
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE