A new bound for the DOL sequence equivalence problem

: Honkala J

Publisher: SPRINGER

: 2007

: Acta Informatica

: ACTA INFORMATICA

: ACTA INFORM

: 43

: 6

: 419

: 429

: 11

: 0001-5903

DOI: https://doi.org/10.1007/s00236-006-0028-6

The DOL sequence equivalence problem consists of deciding, given two morphisms g : X* -> X*, h : X* -> X* and a word w is an element of 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 DOL sequence equivalence problem, it suffices to consider the terms of the sequences with i < 7n(3) root n log n,where n is the cardinality of X.