• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

The Unique Decipherability in the Monoid of Regular Languages is Undecidable

Juhani Karhumäki, Aleksi Saarela, The Unique Decipherability in the Monoid of Regular Languages is Undecidable. Fundamenta Informaticae 110(1-4), 197–200, 2011.

http://dx.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.

BibTeX entry:

@ARTICLE{jKaSa11b,
  title = {The Unique Decipherability in the Monoid of Regular Languages is Undecidable},
  author = {Karhumäki, Juhani and Saarela, Aleksi},
  journal = {Fundamenta Informaticae},
  volume = {110},
  number = {1-4},
  pages = {197–200},
  year = {2011},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication