zbMATH — the first resource for mathematics

Unique decipherability in the additive monoid of sets of numbers. (English) Zbl 1218.68108
Summary: Sets of integers form a monoid, where the product of two sets \(A\) and \(B\) is defined as the set containing \(a+b\) for all \(a \in A\) and \(b \in B\). We give a characterization of when a family of finite sets is a code in this monoid, that is when the sets do not satisfy any nontrivial relation. We also extend this result for some infinite sets, including all infinite rational sets.

68R05 Combinatorics in computer science
68Q45 Formal languages and automata
Full Text: DOI EuDML
[1] J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985). · Zbl 0587.68066
[2] A. Brauer, On a problem of partitions. Amer. J. Math.64 (1942) 299-312. · Zbl 0061.06801
[3] Ch. Choffrut and J. Karhumäki, Unique decipherability in the monoid of languages: an application of rational relations, in Proceedings of the Fourth International Computer Science Symposium in Russia (2009) 71-79. · Zbl 1248.94044
[4] R. Gilmer, Commutative Semigroup Rings. University of Chicago Press (1984). · Zbl 0566.20050
[5] J.-Y. Kao, J. Shallit and Z. Xu, The frobenius problem in a free monoid, in Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (2008) 421-432. · Zbl 1259.68166
[6] J. Karhumäki and L.P. Lisovik, The equivalence problem of finite substitutions on a b * c , with applications. Int. J. Found. Comput. Sci.14 (2003) 699-710. · Zbl 1101.68660
[7] M. Kunc, The power of commuting with finite sets of words. Theor. Comput. Syst.40 (2007) 521-551. · Zbl 1121.68065
[8] D. Perrin, Codes conjugués. Inform. Control. 20 (1972) 222-231. Zbl0254.94015 · Zbl 0254.94015
[9] J.L. Ramírez Alfonsín, The Diophantine Frobenius Problem. Oxford University Press (2005).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.