The Frobenius Problem and Its Generalizations

The classical but oddly little-known Frobenius problem from number theory is the following:  given a set of positive integers with greatest common divisor equal to 1,find the largest integer not representable as a non-negative integer linear combination of the set elements.  This largest integer is called the Frobenius number.  For example,the Frobenius number of 6,9,and 20 is 43.  In this talk I will survey some of the known results on this problem and its applications to computer science,and a new generalization of this problem to words (strings of symbols).

Disciplines : Algèbre et théorie des nombres,Recursive functions
Mots-clés : nombre de Frobenius,théorie complexité,traitement chaîne de caractères
Type de document : image en mouvement
Type de ressource : lecture
Niveau : master,doctorat
Auteurs ou éditeurs : INRIA (Institut national de recherche en informatique et automatique),UNS,CNRS - Centre National de la Recherche Scientifique,Région PACA,INRIA (Institut national de recherche en informatique et automatique),Jeffrey SHALLIT