The sequence equivalence problem for primitive DOL systems

: Honkala J

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2013

: Journal of Computer and System Sciences

: JOURNAL OF COMPUTER AND SYSTEM SCIENCES

: J COMPUT SYST SCI

: 1

: 79

: 1

: 101

: 110

: 10

: 0022-0000

DOI: https://doi.org/10.1016/j.jcss.2012.05.013

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 primitive 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. A smaller bound is obtained for primitive looping morphisms. (C) 2012 Elsevier Inc. All rights reserved.