On well quasi orders of free monoids

AbstractThe paper investigates down-sets associated to well quasi orders. Of particular language-theoretic interest is the quasi order u ⩽sv (resp. u ⩽℘v) of u being a subword (resp. a Parikh subword) of v, as well as their inverses. We establish a number of results about the regularity and effective regularity of the down-sets, in particular, a general condition for the effective regularity of the down-set associated to an inverse well quasi order (Theorem 7.1 ). It is decidable whether or not an arbitrary regular language results as a down-set from an infinite or bi-infinite word, whereas the same problem is undecidable for context-free language. A quasi order being a well quasi order is connected to arbitrary languages being confluent