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

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications

[en]
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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] regularity, bounded delay, Post correspondence problem

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 471 times.
This article's PDF has been downloaded 417 times.