A new bound for the D0L language equivalence problem - UTU Research Portal

A1 Refereed original research article in a scientific journal

A new bound for the D0L language equivalence problem

Authors: Juha Honkala

Publisher: Springer

Publication year: 2018

Journal: Acta Informatica

Volume: 55

Issue: 1

First page : 81

Last page: 88

Number of pages: 8

ISSN: 0001-5903

eISSN: 1432-0525

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

Web address : https://link.springer.com/article/10.1007/s00236-016-0286-x(external)

Self-archived copy’s web address: https://research.utu.fi/converis/portal/Publication/29546226(external)

Abstract

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.