Let Λ∗ be the free monoid of (finite) words over a not necessarily finite alphabet Λ, which is equipped with some (partial) order. This ordering lifts to Λ∗, where it extends the divisibility ordering of words. The MacNeille completion of Λ∗ 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 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 Λ. 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 Λ∗.