Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333010 | Journal of Computer and System Sciences | 2005 | 14 Pages |
Abstract
The ultimate equivalence problem for D0L systems consists of deciding, given two morphisms g:X*â¶X*, h:X*â¶X* and a word wâX*, whether or not gi(w)=hi(w) for all but finitely many i⩾0. We show that for a large class of D0L systems, to decide the ultimate equivalence problem, it suffices to check whether or not gi(w)=hi(w) holds for suitably chosen card(X)2 consecutive values of i.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Juha Honkala,