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.

Last updated on 26/11/2024 02:25:53 PM