SOME RESULTS ON CAPABILITIES OF ONEDIMENSIONAL ITERATIVE LOGICAL NETWORKS AND THEIR RELATED PROBLEMS.

Abstract

Results on capabilities of one-dimensional systems of iterative logical networks are presented. It is shown that (1) Kilmer's result (AD-425 943) implies a positive answer to Hennie's conjecture ('Iterative arrays of logical circuits,' MIT Press, Cambridge, Mass. 1961) that the unilateral systems which are stable in the wide sense are more powerful than the strictly stable unilateral systems, (2) the unilateral systems which are stable in the wide sense are more powerful then the nondeterministic push-down automata, (3) the strictly stable unilateral systems are more powerful than the deterministic push-down automata and (4) a proper subclass of strictly stable unilateral systems is more powerful in a sense than the class of two-tape one-way automata. It also is proved that (1) a language generated by a linear grammar is n squared-recognizable by a single-tape Turing machine in the sense of Hartmanis and Stearns ('Computational complexity of recursive sequences.' Proc. Fifth Annual Symposium of Switching Circuit Theory and Logical Design', (Oct. 1964) p. 82-90) and (2) there is a language which is generated by a linear grammar and is not n-recognizable. (Author)

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1965
Accession Number
AD0626733

Entities

People

  • Tadao Kasami

Organizations

  • University of HawaiĘ»i System

Tags

DTIC Thesaurus Topics

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

Readers

  • Mathematical Modeling and Probability Theory.