A1 Refereed original research article in a scientific journal

The Unique Decipherability in the Monoid of Regular Languages is Undecidable



Authors: Karhumaki J, Saarela A

Publisher: IOS PRESS

Publication year: 2011

Journal: Fundamenta Informaticae

Journal name in source: FUNDAMENTA INFORMATICAE

Journal acronym: FUND INFORM

Number in series: 1-4

Volume: 110

Issue: 1-4

First page : 197

Last page: 200

Number of pages: 4

ISSN: 0169-2968

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


Abstract
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