Juhani Karhumaki ; Aleksi Saarela - Noneffective Regularity of Equality Languages and Bounded Delay Morphisms

dmtcs:523 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 4 - https://doi.org/10.46298/dmtcs.523
Noneffective Regularity of Equality Languages and Bounded Delay MorphismsArticle

Authors: Juhani Karhumaki 1; Aleksi Saarela ORCID1

  • 1 Turku Centre for Computer Science

We give an instance of a class of morphisms for which it is easy to prove that their equality set is regular, but its emptiness is still undecidable. The class is that of bounded delay 2 morphisms.

https://doi.org/10.46298/dmtcs.523
Source: HAL:hal-00990433v1
Volume: Vol. 12 no. 4
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: regularity,bounded delay,Post correspondence problem,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 381 times.
This article's PDF has been downloaded 314 times.