A new bound for the D0L language equivalence problem



: Juha Honkala

Publisher: Springer

: 2018

: Acta Informatica

: 55

: 1

: 81

: 88

: 8

: 0001-5903

: 1432-0525

DOI: https://doi.org/10.1007/s00236-016-0286-x

: https://link.springer.com/article/10.1007/s00236-016-0286-x

: https://research.utu.fi/converis/portal/Publication/29546226


We study the language equivalence problem for smooth and loop-free D0L systems. We show that the number of initial terms in the associated D0L sequences we have to consider to decide language equivalence depends only on the cardinality of the underlying alphabet.



Last updated on 2024-26-11 at 20:35