Accession Number : AD0649063

Title :   REALIZATION AND COMPLEXITY OF COMMUTATIVE EVENTS.

Descriptive Note : Technical rept.,

Corporate Author : MICHIGAN UNIV ANN ARBOR LOGIC OF COMPUTERS GROUP

Personal Author(s) : Laing,Richard

Report Date : MAR 1967

Pagination or Media Count : 44

Abstract : A measure of complexity is defined for a class of expressions denoting behaviors of commutative machines. For an expression of complexity m there is an m tape machine which realizes in real-time the event denoted. The machine realizations can be of many kinds; the 'simplest' realizations are those composed of finite counters of a single kind of input letter, combined with infinite state machines which check off numbers (mod p) of one kind of input letter against numbers (mod r) of a second kind of input letter. The state diagrams of the finite state machines are in the form of cycles (possibly with linear 'lead-ins'); the state diagrams of the infinite state machines graphically are infinite cylinders (possibly with two-dimensional lead in arrays). For any machine with m counter tapes (as here defined), an m-complex expression can be obtained which denotes the event which is the behavior of the machine. Finally it is shown that for all m there are m-complex expressions which require m-counter tape machines for realizing in real-time the events denoted. (Author)

Descriptors :   (*AUTOMATION, *COMBINATORIAL ANALYSIS), MACHINES, REAL TIME, MATHEMATICAL LOGIC, MEASURE THEORY, COUNTING METHODS, COMPUTER LOGIC, COMPLEX NUMBERS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE