A Decision Procedure for Computations of Finite Automata
Joyce Friedman · Journal of the ACM · 1962
The "computed output sequence" of a finite automaton is defined as the sequence which results from the output sequence when all occurrences of a special output symbol X are deleted.A "computation pair" consists of an input sequence and the resultant computed output sequence, and the "computation" of an automaton is the set of all its computation pairs.The class of infinite computations is broader than the class of behaviors of finite automata.Burks has therefore raised the question of the existence of a decision procedure to determine if two automata have the same computation.In this paper, such a decision procedure is given.