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

: Honkala J

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2005

: JOURNAL OF COMPUTER AND SYSTEM SCIENCES

: J COMPUT SYST SCI

: 71

: 4

: 506

: 519

: 14

: 0022-0000

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

The ultimate equivalence problem for DOL systems consists of deciding, given two morphisms g : X* -> X*, h : X* -> X* and a word omega is an element of X*, whether or not g(i)(omega) = h(i)(omega) for all but finitely many i >= 0. We show that for a large class of DOL systems, to decide the ultimate equivalence problem, it suffices to check whether or not g(i)(omega) = h(i)(omega) holds for suitably chosen card(X)(2) consecutive values of i. (c) 2005 Elsevier Inc. All rights reserved.