On infinite words generated by polynomial DOL systems

: Honkala J

Publisher: ELSEVIER SCIENCE BV

: 2002

: Discrete Applied Mathematics

: DISCRETE APPLIED MATHEMATICS

: DISCRETE APPL MATH

: 116

: 3

: 297

: 305

: 9

: 0166-218X

DOI: https://doi.org/10.1016/S0166-218X(01)00231-1

We study infinite words generated by polynomially bounded D0L systems and the relations between equivalent and omega-equivalent D0L systems. As the main result we show that if two polynomially bounded D0L systems G(i) = (X, h(i), w), i = 1, 2, are omega-equivalent, then there exist an integer t greater than or equal to 0 and t-tuples (i(1),...,i(iota)) (j(1),..., j(iota)) such that the systems H-1 = (X, h(1)h(1)...h(t), w) and H-2 = (X, h(2)h(j1)...h(jt), w) are nearly equivalent in the sense that they generate the same word sequences if certain suffixes of restricted lengths are disregarded. (C) 2002 Elsevier Science B.V. All rights reserved.