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(external)


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 2024-26-11 at 10:23