Let $��^{\ast}$ be the free monoid of (finite) words over a not necessarily finite alphabet $��$, which is equipped with some (partial) order. This ordering lifts to $��^{\ast}$, where it extends the divisibility ordering of words. The MacNeille completion of $��^{\ast}$ constitutes a complete lattice ordered monoid and is realized by the system of "closed" lower sets in $��^*$ (ordered by inclusion) or its isomorphic copy formed of the "closed" upper sets (ordered by reverse inclusion). Under some additional hypothesis on $��$, one can easily identify the closed lower sets as the finitely generated ones, whereas it is more complicated to determine the closed upper sets. For a fairly large class of ordered sets $��$ (including complete lattices as well as antichains) one can generate the closure of any upper set of words by means of binary operations ( "syntactic rules") thus obtaining an efficient procedure to test closedness. Closed upper set of words are involved in an embedding theorem for valuated oriented graphs. In fact, generalized paths (so-called "zigzags") are encoded by words over an alphabet $��$. Then the valuated oriented graphs which are "isometrically" embeddable in a product of zigzags have the characteristic property that the words corresponding to the zigzags between any pair of vertices form a closed upper set in $��$.

18pages, 3 figures