An n2-bound for the ultimate equivalence problem of certain D0L systems over an n-letter alphabet

摘要

The ultimate equivalence problem for D0L systems consists of deciding, given two morphisms g:X*⟶X*, h:X*⟶X* and a word w∈X*, whether or not gi(w)=hi(w) for all but finitely many i⩾0. We show that for a large class of D0L systems, to decide the ultimate equivalence problem, it suffices to check whether or not gi(w)=hi(w) holds for suitably chosen card(X)2 consecutive values of i.