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.

decidability, DOL systems, equivalence problem, infinite words