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

作者：Choffrut Christian^*; Karhumaki Juhani

来源：Theory of Computing Systems, 2011, 49(2): 355-364.

DOI：10.1007/s00224-011-9324-9

• Unique decipherability
• Finite automata
• Regular languages

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 na parts per thousand yen1. 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.

• 出版日期2011-8