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
Noneffective Regularity of Equality Languages and Bounded Delay Morphisms

Authors: Juhani Karhumaki ; Aleksi Saarela

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.


Volume: Vol. 12 no. 4
Published on: January 1, 2010
Submitted on: March 26, 2015
Keywords: regularity,bounded delay,Post correspondence problem,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 97 times.
This article's PDF has been downloaded 141 times.