Unique decipherability in the additive monoid of sets of numbers
Saarela, Aleksi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011), p. 225-234 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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∈A and b∈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.

Publié le : 2011-01-01
DOI : https://doi.org/10.1051/ita/2011018
Classification:  68R05,  68Q45 
@article{ITA_2011__45_2_225_0,
     author = {Saarela, Aleksi},
     title = {Unique decipherability in the additive monoid of sets of numbers},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {45},
     year = {2011},
     pages = {225-234},
     doi = {10.1051/ita/2011018},
     mrnumber = {2811655},
     zbl = {1218.68108},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2011__45_2_225_0}
}

Saarela, Aleksi. Unique decipherability in the additive monoid of sets of numbers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) pp. 225-234. doi : 10.1051/ita/2011018. http://gdmltest.u-ga.fr/item/ITA_2011__45_2_225_0/

[1] J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985). | MR 797069 | Zbl 0587.68066

[2] A. Brauer, On a problem of partitions. Amer. J. Math. 64 (1942) 299-312. | MR 6196 | 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). | MR 741678 | 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. | MR 2873754 | Zbl 1259.68166

[6] J. Karhumäki and L.P. Lisovik, The equivalence problem of finite substitutions on ab * c, with applications. Int. J. Found. Comput. Sci. 14 (2003) 699-710. | MR 2010592 | Zbl 1101.68660

[7] M. Kunc, The power of commuting with finite sets of words. Theor. Comput. Syst. 40 (2007) 521-551. | MR 2305376 | Zbl 1121.68065

[8] D. Perrin, Codes conjugués. Inform. Control. 20 (1972) 222-231. | MR 345711 | Zbl 0254.94015

[9] J.L. Ramírez Alfonsín, The Diophantine Frobenius Problem. Oxford University Press (2005). | MR 2260521 | Zbl 1134.11012