A new bound for the D0L sequence equivalence problem

摘要

The D0L sequence equivalence problem consists of deciding, given two morphisms g : X~* → X~*, h : X~* → X~* and a word w ∈ X~*, whether or not g~i(w) = h~i(w) for all i ≥ 0. We show that in case of smooth and loop-free morphisms, to decide the D0L sequence equivalence problem, it suffices to consider the terms of the sequences with i < 7n~3 (n log n)~(1/2), where n is the cardinality of X.