Let Lambda be the free monoid of (finite) words over a not necessarily finite alphabet Lambda, which is equipped with some (partial) order. This ordering lifts to Lambda, where it extends the divisibility ordering of words. The MacNeille completion of Lambda constitutes a complete lattice ordered monoid and is realized by the system of closed lower sets in Lambda (ordered by inclusion) or its isomorphic copy formed of the closed upper sets (ordered by reverse inclusion). Under some additional hypothesis on Lambda, 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 Lambda (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 sets 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 Lambda. 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 Lambda.