PERIODIC SETS OF INTEGERS

Consider the following kinds of sets: the set of all possible distance s between two vertices of a directed graph; any set of integers that i s either finite or periodic for all n greater or equal to some no (suc h a set is called ultimately periodic); a context-free language over a n alphabet with one letter (such a language is also regular); the set of all possible lengths of words of a context-free language. All these sets are isomorphic relatively to the operations of union (or sum), c oncatenation and Kleene (or transitive) closure. Furthermore, they all share a particularly important property which is not valid in some si milar algebraic structure - the concatenation is commutative. The purp ose of this paper is to investigate the representation and properties of these sets and also the algorithms to compute the operations mentio ned above. The concepts of linear number and DELTA-sum are developed i n order to provide convenient methods of representation and manipulati on. It should be noted that although DELTA-sums and regular expression s (or finite automata) over a one-letter alphabet denote essentially t he same sets, the corresponding algebras are quite different. For exam ple, it is always possible to eliminate the closure and concatenation operations from a DELTA-sum by expanding it as a sum of linear numbers . No such elimination is possible for regular expressions (although sp ecial forms of regular expressions or finite automata are sufficient t o denote regular sets over one-letter alphabets). The algorithms using DELTA-sums are often faster and simpler than those based on finite au tomata or regular expressions over a one-letter alphabet. We think tha t this improvement comes from the fact that a set of words over one le tter is represented by the set of their lengths and manipulated by ari thmetic operations. We apply these methods to the first kind of sets l isted above and present new algorithms dealing with a variety of probl ems related to distances in directed graphs.