A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
An n(2)-bound for the ultimate equivalence problem of certain D0L systems over an n-letter alphabet
Tekijät: Honkala J
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2005
Tietokannassa oleva lehden nimi: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Lehden akronyymi: J COMPUT SYST SCI
Vuosikerta: 71
Numero: 4
Aloitussivu: 506
Lopetussivu: 519
Sivujen määrä: 14
ISSN: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2005.05.003
Tiivistelmä
The ultimate equivalence problem for DOL systems consists of deciding, given two morphisms g : X* -> X*, h : X* -> X* and a word omega is an element of X*, whether or not g(i)(omega) = h(i)(omega) for all but finitely many i >= 0. We show that for a large class of DOL systems, to decide the ultimate equivalence problem, it suffices to check whether or not g(i)(omega) = h(i)(omega) holds for suitably chosen card(X)(2) consecutive values of i. (c) 2005 Elsevier Inc. All rights reserved.
The ultimate equivalence problem for DOL systems consists of deciding, given two morphisms g : X* -> X*, h : X* -> X* and a word omega is an element of X*, whether or not g(i)(omega) = h(i)(omega) for all but finitely many i >= 0. We show that for a large class of DOL systems, to decide the ultimate equivalence problem, it suffices to check whether or not g(i)(omega) = h(i)(omega) holds for suitably chosen card(X)(2) consecutive values of i. (c) 2005 Elsevier Inc. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali