A new bound for the D0L language equivalence problem - UTU Tutkimustietojärjestelmä

A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

A new bound for the D0L language equivalence problem

Tekijät: Juha Honkala

Kustantaja: Springer

Julkaisuvuosi: 2018

Journal: Acta Informatica

Vuosikerta: 55

Numero: 1

Aloitussivu: 81

Lopetussivu: 88

Sivujen määrä: 8

ISSN: 0001-5903

eISSN: 1432-0525

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

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

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

Tiivistelmä

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.