Accession Number : AD0696085

Title :   ON THE COMPUTATIONAL COMPLEXITY OF FINITE FUNCTIONS.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF STANFORD ELECTRONICS LABS

Personal Author(s) : Spira,Philip M.

Report Date : MAY 1968

Pagination or Media Count : 73

Abstract : One of the most rapidly expanding fields of applied mathematics and engineering is automata theory. Although the term 'automaton' is derived from 'self-moving thing,' the prime concern of automata theory is the study of information-processing devices. A specific example of information processing is computation, and thus the mathematical properties of devices which perform computations are of interest to automata theorists. In this thesis we investigate the computation by logic circuits of a certain class of functions having finite domain. To a given function f a number of so-called complexity criteria can be assigned relative to that class, e.g., the minimum computation time of or the minimum number of elements contained in any circuit of the class which is capable of computing f. Our prime criterion of interest will be computation time. (Author)

Descriptors :   (*LEARNING MACHINES, COMPUTER LOGIC), (*COMPUTER PROGRAMMING, FUNCTIONS(MATHEMATICS)), (*FUNCTIONS(MATHEMATICS), NUMERICAL ANALYSIS), MATHEMATICAL LOGIC, LOGIC CIRCUITS, GROUPS(MATHEMATICS), AUTOMATA, THESES

Subject Categories : Computer Programming and Software
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE