Realization of Input-Output Relations by Sequential Machines

ABSTRACT

This paper deals with the synthesis of sequential machines (without a distinguished initial state) which satisfies a specified list of input sequences and corresponding output sequences. Readily testable necessary and sufficient conditions are given for such a list to result in a realizable machine, and an algorithm is formulated for constructing the machine when these conditions are fulfilled.

REFERENCES

• 1: MEALY, G. H. Method for synthesizing sequential circuits. Bell Sys. Tech. J. 84, (1955), 1045-1079.
• 2: GILL, A. Introduction to the Theory of Finite-State Machines. McGraw-Hill, New York, 1962.
• 3: TAL, A. A. Questionaire language and abstract synthesis of minimum sequential machines. Avtomatika i Telemekhanika 25 (1964), 946-962.
• 4: MOORE, E.F. Oedanken-experiments in sequential machines, pp. 129-153. Automata Studies, Princeton U. Press, 1956.
• 5: GILL, A. :Relational equivalerme of sequential machines. Notes on System Theory, Vol. VI, Electronics Res. Lab., U. of California, 1964.f

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Algorithms, Measurement, Performance, Theory, Verification