A1 Refereed original research article in a scientific journal
The sequence equivalence problem for primitive DOL systems
Authors: Honkala J
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2013
Journal: Journal of Computer and System Sciences
Journal name in source: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Journal acronym: J COMPUT SYST SCI
Number in series: 1
Volume: 79
Issue: 1
First page : 101
Last page: 110
Number of pages: 10
ISSN: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2012.05.013
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 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.
UTU Research Portal