A1 Refereed original research article in a scientific journal
A new bound for the DOL sequence equivalence problem
Authors: Honkala J
Publisher: SPRINGER
Publication year: 2007
Journal: Acta Informatica
Journal name in source: ACTA INFORMATICA
Journal acronym: ACTA INFORM
Volume: 43
Issue: 6
First page : 419
Last page: 429
Number of pages: 11
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s00236-006-0028-6
Abstract
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.
UTU Research Portal