[seqfan] equality testing automatic sequences
fred.lunnon at gmail.com
Mon Oct 16 16:30:07 CEST 2017
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) ?
More information about the SeqFan