A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
The sequence equivalence problem for primitive DOL systems
Tekijät: Honkala J
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2013
Journal: Journal of Computer and System Sciences
Tietokannassa oleva lehden nimi: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Lehden akronyymi: J COMPUT SYST SCI
Numero sarjassa: 1
Vuosikerta: 79
Numero: 1
Aloitussivu: 101
Lopetussivu: 110
Sivujen määrä: 10
ISSN: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2012.05.013
Tiivistelmä
The DOL sequence equivalence problem consists of deciding, given. two morphisms g: X* -> X*, h: X* -> X* and a word w is an element of X*, whether or not g(i)(w) = h(i)(w) for all i >= 0. We show that in case of primitive morphisms, to decide the DOL sequence equivalence problem, it suffices to consider the terms of the sequences with i < 7n(3)root n log n, where n is the cardinality of X. A smaller bound is obtained for primitive looping morphisms. (C) 2012 Elsevier Inc. All rights reserved.
The DOL sequence equivalence problem consists of deciding, given. two morphisms g: X* -> X*, h: X* -> X* and a word w is an element of X*, whether or not g(i)(w) = h(i)(w) for all i >= 0. We show that in case of primitive morphisms, to decide the DOL sequence equivalence problem, it suffices to consider the terms of the sequences with i < 7n(3)root n log n, where n is the cardinality of X. A smaller bound is obtained for primitive looping morphisms. (C) 2012 Elsevier Inc. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali