The Unique Decipherability in the Monoid of Regular Languages is Undecidable

• Autorzy: Karhumäki J. , Saarela A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

unique decipherability problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 197--200
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Karhumäki J.

autor

Saarela A.

• Department ofMathematics and Turku Centre for Computer Science TUCS, University of Turku, FI-20014 Turku, Finland,

Bibliografia

• [1] Jean Berstel and Dominique Perrin. Theory of Codes. Academic Press, 1985.
• [2] Christian Choffrut, Tero Harju, and Juhani Karhumäki. A note on decidability questions on presentations of word semigroups. Theoret. Comput. Sci., 183(1):83-92, 1997.
• [3] Christian Choffrut and Juhani Karhumäki. Unique decipherability in the monoid of languages: an application of rational relations. Theory Comput. Syst., 49(2):355-364, 2011.
• [4] Marek Chrobak and Wojciech Rytter. Unique decipherability for partially commutative alphabet. Fund. Inform., 10(3):323-336, 1986.
• [5] Tero Harju and Juhani Karhumäki. Morphisms. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, volume 1, pages 439-510. Springer-Verlag, 1997.
• [6] David A. Klarner, Jean-Camille Birget, and Wade Satterfield. On the undecidability of the freeness of integer matrix semigroups. Internat. J. Algebra Comput., 1(2):223-226, 1991.
• [7] Aleksi Saarela. Unique decipherability in the additive monoid of sets of numbers. RAIRO Inform. Theor. Appl. To appear.
• [8] August Albert Sardinas and GeorgeW. Patterson. A necessary and sufficient condition for unique decomposition of coded messages. In IRE Intern. Conv. Rec. 8 (1953), pages 104-108. Chapman and Hall, 1953