The Unique Decipherability in the Monoid of Regular Languages is Undecidable



: Karhumaki J, Saarela A

Publisher: IOS PRESS

: 2011

 Fundamenta Informaticae

: FUNDAMENTA INFORMATICAE

: FUND INFORM

: 1-4

: 110

: 1-4

: 197

: 200

: 4

: 0169-2968

DOI: https://doi.org/10.3233/FI-2011-537


We show by a simple reduction that the unique decipherability problem in the language monoid of regular languages over a non-unary alphabet is undecidable.



Last updated on 26/11/2024 10:23:42 AM