The ultimate equivalence problem for DOL systems

Summary The ultimate equivalence problem for DOL systems is shown to be recursively decidable. In algebraic formulation this problem can be stated as follows: Given finite alphabet , two homomorphisms h ₁ and h ₂ on the free monoid ^* and two words w ₁ w ₂ in ^*, does there exist m0 so that h ₁ ⁿ (w ₁) = h ₂ ⁿ (w ₂) for all nm?This research was supported by the National Research Council of Canada, Grant No. A7403, and most of it has been done during the author's stay at the University of Karlsruhe, Karlsruhe, Germany (Fed. Rep.)