
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 realtime 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 'leadins'); the state diagrams of the infinite state machines graphically are infinite cylinders (possibly with twodimensional lead in arrays). For any machine with m counter tapes (as here defined), an mcomplex 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 mcomplex expressions which require mcounter tape machines for realizing in realtime 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