Sequential Machines, Ambiguity, and Dynamic Programming

ABSTRACT

Given a sequential machine, in the terminology of E. F. Moore, Annals of Mathematics Studies, No. 34, 1956, a problem of some interest is that of determining testing procedures which will enable one to transform it into a known state starting from an initial situation in which only the set of possible states is given. To treat this problem, we introduce the concept of ambiguity, and show how the functional equation approach of dynamic programming can be applied.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 2: Richard Bellman , John Holland , Robert Kalaba, On an Application of Dynamic Programming to the Synthesis of Logical Systems, Journal of the ACM (JACM), v.6 n.4, p.486-493, Oct. 1959 [doi>10.1145/320998.321002]
• 3: S. GINSBURG, On the length of the smallest uniform experiment which distinguishes the terminal states of a machine, Research Report, The National Cash Register Company, Electronics Division, Hawthorne, California, 1957.
• 4: S. HUZINO, "On some sequential machines and experiments," Memoirs of Fac. Sci., Kyushu Univ., Ser. A, Vol. XII, No. 2, 1958.
• 5: G. H. MEALY, A method for synthesizing sequential circuits, Bell System Tech. dr. ~ (1955), 1045-1079.
• 6: E. F. MOORE, "Gedanken-experiments on sequential machines," in Automata Studies, Annals of Mathematics Series, No. 34, 1956, pp. 129-153.

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)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Design, Performance, Theory