Refereed journal article or data article (A1)
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
Start page: 297
End page: 305
Number of pages: 9
ISSN: 0166-218X
DOI: http://dx.doi.org/10.1016/S0166-218X(01)00231-1
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.
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.
UTU Research Portal