[seqfan] equality testing automatic sequences

[Fred Lunnon]

  Given two distinct CD0L morphic systems, each comprising inflation
morphism + initial state + encoding morphism: what is an efficient
algorithm to determine whether they generate the same automatic sequence;
and what bound is available on its time complexity, in terms of inflation
widths  w1, w2  and state counts  q1, q2  of the systems?

  A simple-minded method constructs their Cartesian product,
then iterates that until every state pair has been generated,
checking that each code pair is consistent; time bound is of
order  w^q , where  w = max(w1, w2)  and  q = q1 q2 .

  Can this bound be sharpened: perhaps to  q = max(q1, q2) ?

Fred Lunnon