Discrete Mathematics & Theoretical Computer Science, Vol 12, No 4 (2010)

Font Size:  Small  Medium  Large

Noneffective Regularity of Equality Languages and Bounded Delay Morphisms

Juhani Karhumäki, 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.

Full Text: PDF PostScript