A Language-Theoretic Approach to Covering Problems

The formal language of all words 'covered' by words in a given language is investigated. A language is a covering code when any word has at most one minimal covering over it; in this case the language generated by the covering operation is said cov-free. We study the notion of cov-freeness, in analogy to the theory developed on classical freeness. In particular cov-freeness is characterized by the notion of cov-stability introduced here. Further, cov-maximality of a regular covering code is characterized by its cov-completeness. Some more properties are obtained using these characterizations. We also show that the series counting the minimal coverings of a word over a regular language is rational. All along the paper we compare new definitions and results to their counterpart in classical monoids and in monoids of zig-zag factorizations.