A1 Refereed original research article in a scientific journal
An n(2)-bound for the ultimate equivalence problem of certain D0L systems over an n-letter alphabet
Authors: Honkala J
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2005
Journal name in source: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Journal acronym: J COMPUT SYST SCI
Volume: 71
Issue: 4
First page : 506
Last page: 519
Number of pages: 14
ISSN: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2005.05.003
Abstract
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.
UTU Research Portal