Marked D0L systems and the 2n-conjecture



: Honkala J

Publisher: ELSEVIER SCIENCE BV

: 2012

 Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 432

: 94

: 97

: 4

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2012.01.037


We show that to test the equivalence of two D0L sequences over an en-letter alphabet generated by marked morphisms it suffices to compare the first.2n + 1 initial terms of the sequences. Under an additional condition it is enough to consider the 2n initial terms. (C) 2012 Elsevier B.V. All rights reserved.


D0L sequence equivalence problem, D0L system, Decidability, Marked morphism



Last updated on 26/11/2024 11:24:05 AM