Noneffective Regularity of Equality Languages and Bounded Delay Morphisms

: Juhani Karhumäki, Aleksi Saarela

Publisher: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE

: 2010

: Discrete Mathematics and Theoretical Computer Science

: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE

: DISCRETE MATH THEOR

: 4

: 12

: 4

: 9

: 17

: 9

: 1462-7264

: http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1451

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.

Mathematics

kasa10dmtcs.pdf