The ω sequence problem for DOL systems is decidable

Reviewer: Michael Hanns Heinrich Kunze

This paper solves the decision problem in the title. Let &Sgr; be an alphabet and &sgr; 1,&sgr; 2 :9I &sgr; *. The question is to decide whether iterated application of prefix-preserving homomorphism h 1, respectively h 2: &Sgr; * :9I &Sgr; * to &sgr;:0O1, respectively ultimately produces the same &ohgr;-word. As a first step the problem is reduced to the special case of normal 1-systems. Then simple systems are introduced and finally the general case is reduced to certain 1-simple normal systems. A crucial point is to prove that these systems, derived from limit language equivalent normal 1-systems, have bounded balance. The proof of the latter fact requires some matrix theory. Overall, the techniques involved are a considerable refinement of those used to solve the ordinary DOL sequence equivalence problem. The &ohgr;-sequence equivalence problem was previously posed by Culik and Salomaa [1]. By that time it was already clear that there is no easy solution for the Go-sequence problem because it implies a solution of the ordinary problem immediately, but not vice versa. Thus, this is certainly an important paper with a beautiful result. But mathematically, as often happens when a fairly technical (though well organized) proof of a major result is presented, one wonders if it might not be possible to circumvent long technical arguments by some structured theory, which is both more enlightening and enjoyable to read.