Deciding atomicity of subword-closed languages

We study languages closed under the non-contiguous (scattered) subword containment order. Any subword-closed language L can be uniquely described by its anti-dictionary, i.e. the set of minimal words that do not belong to L. For a language over a finite alphabet, the anti-dictionary is necessarily finite. A language L is said to be atomic if it cannot be presented as the union of two subword-closed languages different from L. In this work, we provide a decision procedure which, given a language over a finite alphabet defined by its anti-dictionary, decides whether it is atomic or not. We also develop an algorithmic procedure for decomposing a language, which is not atomic, into finitely many atomic sublanguages.