A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A new bound for the DOL sequence equivalence problem
Tekijät: Honkala J
Kustantaja: SPRINGER
Julkaisuvuosi: 2007
Journal: Acta Informatica
Tietokannassa oleva lehden nimi: ACTA INFORMATICA
Lehden akronyymi: ACTA INFORM
Vuosikerta: 43
Numero: 6
Aloitussivu: 419
Lopetussivu: 429
Sivujen määrä: 11
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s00236-006-0028-6
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 smooth and loop-free 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.
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 smooth and loop-free 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.
Turun yliopiston Tutkimustietojärjestelmän portaali