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.


Internal Authors/Editors

Last updated on 2019-14-06 at 12:49