A1 Journal article – refereed

On infinite words generated by polynomial DOL systems

List of Authors: Honkala J

Publisher: ELSEVIER SCIENCE BV

Publication year: 2002

Journal: Discrete Applied Mathematics

Journal name in source: DISCRETE APPLIED MATHEMATICS

Journal acronym: DISCRETE APPL MATH

Volume number: 116

Issue number: 3

Number of pages: 9

ISSN: 0166-218X

Abstract

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.