Karhumaki, Juhani and Saarela, Aleksi - 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: Karhumaki, Juhani and Saarela, Aleksi

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.


Source : oai:HAL:hal-00990433v1
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 50 times.
This article's PDF has been downloaded 68 times.