A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On infinite words generated by polynomial DOL systems
Tekijät: Honkala J
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2002
Lehti: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: DISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Vuosikerta: 116
Numero: 3
Aloitussivu: 297
Lopetussivu: 305
Sivujen määrä: 9
ISSN: 0166-218X
DOI: https://doi.org/10.1016/S0166-218X(01)00231-1
Tiivistelmä
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.
Avainsanat:
decidability, DOL systems, equivalence problem, infinite words
Turun yliopiston Tutkimustietojärjestelmän portaali