Circuits of Finite Memory Retrospective Operators
by
Alexandre P. Francisco
CLC/DEI, Instituto Superior Técnico, Taguspark, 2780-990 Porto Salvo, PORTUGAL

The research around automata over continuous time, started by B. A. Trakhtenbrot and A. Rabinovich, is expanded in this work, where we succeed to develop a theory of circuits of retrospective operators to fully characterize the class of finite memory retrospective operators.

In this work we introduce a theory of circuits of finite memory retrospective operators to fully characterize the class of finite memory retrospective operators, expanding the theory developed by B. A. Trakhtenbrot and A. Rabinovich about automata over continuous time. A physical device, in which complex transformations are implemented, is usually an appropriate combination of elementary parts that interact as desired.

These ideas conduct us to the concept of circuit which appears many times in literature. Our main contribution to this theory is the introduction of circuits of finite memory retrospective operators over signals, i.e., we choose a set of elementary finite memory operators and we study how to obtain all finite memory retrospective operators by constructing circuits with the elementary operators.

The concept of function algebra is used in order to obtain an algebra of finite memory retrospective operators and we prove the equivalence between this algebra of operators and the set of finite memory retrospective operators.

It is important to note that we do not use time delay operators, which are commonly used in the classical theory of circuits. In order to know the values of signals at previous instants we use the LLim operator and the LJV operator and with these operators we prove that it is possible construct circuits for any finite memory retrospective operator.

Examples of circuits for some operators are also included. The general construction schema provided in the proof of the main result permits the construction of circuits for any finite memory retrospective operator using the function algebra.

Date received: April 4, 2003