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

Unique Decipherability in the Monoid of Languages: An Application of Rational Relations

Christian Choffrut, Juhani Karhumäki, Unique Decipherability in the Monoid of Languages: An Application of Rational Relations. Theory of Computing Systems 49(2), 355–364, 2011.

http://dx.doi.org/10.1007/s00224-011-9324-9

Abstract:

We attack the problem of deciding whether a finite collection of finite languages is a code, that is, possesses the unique decipherability property in the monoid of finite languages. We investigate a few subcases where the theory of rational relations can be employed to solve the problem. The case of unary languages is one of them and as a consequence, we show how to decide for two given finite subsets of nonnegative integers, whether they are the nth root of a common set, for some n≥1. We also show that it is decidable whether a finite collection of finite languages is a Parikh code, in the sense that whenever two products of these sets are commutatively equivalent, so are the sequences defining these products. Finally, we consider a nonunary special case where all finite sets consist of words containing exactly one occurrence of the specific letter.

BibTeX entry:

@ARTICLE{jChKa11a,
  title = {Unique Decipherability in the Monoid of Languages: An Application of Rational Relations},
  author = {Choffrut, Christian and Karhumäki, Juhani},
  journal = {Theory of Computing Systems},
  volume = {49},
  number = {2},
  pages = {355–364},
  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