Unique decipherability in the additive monoid of sets of numbers

Aleksi Saarela

RAIRO - Theoretical Informatics and Applications (2011)

  • Volume: 45, Issue: 2, page 225-234
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Saarela, Aleksi. "Unique decipherability in the additive monoid of sets of numbers." RAIRO - Theoretical Informatics and Applications 45.2 (2011): 225-234. <http://eudml.org/doc/276337>.

@article{Saarela2011,
abstract = { 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. },
author = {Saarela, Aleksi},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Unique decipherability; rational set; sumset; unique decipherability},
language = {eng},
month = {6},
number = {2},
pages = {225-234},
publisher = {EDP Sciences},
title = {Unique decipherability in the additive monoid of sets of numbers},
url = {http://eudml.org/doc/276337},
volume = {45},
year = {2011},
}

TY - JOUR
AU - Saarela, Aleksi
TI - Unique decipherability in the additive monoid of sets of numbers
JO - RAIRO - Theoretical Informatics and Applications
DA - 2011/6//
PB - EDP Sciences
VL - 45
IS - 2
SP - 225
EP - 234
AB - 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.
LA - eng
KW - Unique decipherability; rational set; sumset; unique decipherability
UR - http://eudml.org/doc/276337
ER -

References

top
  1. J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985).  
  2. A. Brauer, On a problem of partitions. Amer. J. Math.64 (1942) 299–312.  
  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.  
  4. R. Gilmer, Commutative Semigroup Rings. University of Chicago Press (1984).  
  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.  
  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.  
  7. M. Kunc, The power of commuting with finite sets of words. Theor. Comput. Syst.40 (2007) 521–551.  
  8. D. Perrin, Codes conjugués. Inform. Control. 20 (1972) 222–231.  
  9. J.L. Ramírez Alfonsín, The Diophantine Frobenius Problem. Oxford University Press (2005).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.