A subsequence of a word w is a word u such that u = w [ i 1 ] w [ i 2 ] … w [ i k ] , for some set of indices 1 ≤ i 1 < i 2 < … < i k ≤ | w | . A word w is k -subsequence universal over an alphabet Σ if every word in Σ k appears in w as a subsequence. In this paper, we study the intersection between the set of k -subsequence universal words over some alphabet Σ and regular languages over Σ. We call a regular language L k- ∃ -subsequence universal if there exists a k -subsequence universal word in L , and k- ∀ -subsequence universal if every word of L is k -subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is k- ∃ -subsequence universal and, respectively, if it is k- ∀ -subsequence universal , for a given k . The algorithms are FPT w.r.t. the size of the input alphabet, and their run-time does not depend on k ; they run in polynomial time in the number n of states of the input automaton when the size of the input alphabet is O ( log ⁡ n ) . Moreover, we show that the problem of deciding if a given regular language is k- ∃ -subsequence universal is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of k -subsequence universal words (paths) accepted by a given deterministic (respectively, non-deterministic) finite automaton, and ranking an input word (path) within the set of k -subsequence universal words accepted by a given finite automaton.

One of the most studied famous classes of words is the class of Lyndon words. Their studies are mainly motivated by the property that they factorise the free monoid as shown in the famous Chen-Fox-Lyndon Theorem. Several generalisations of Lyndon words as anti-Lyndon words, Nyldon words or inverse Lyndon words were made over time. In 2014, Grinberg introduced Nyldon words as a new perspective on the factorisation of the free monoid of words. In particular, for Nyldon words the famous Chen-Fox-Lyndon Theorem is considered w.r.t. a reversed lexicographical order, i.e., a lexicographically non-decreasing factorisation where each factor is smaller or equal than its successor. Further, a generalised lexicographical order is defined by equipping each position i in a word in Σ ⁎ with a total order ◃ i on Σ. For combining the concept of a generalised order as for generalised Lyndon words and the class of Nyldon words, we investigate a non-decreasing factorisation of the free monoid w.r.t. this generalised ordering and introduce generalised Nyldon words . We show that those words even force a unique non-decreasing factorisation, form a right Hall set, and coincide with the anti-Lyndon words.

A subsequence of a word w is a word u such that u = w[i₁] w[i₂] … w[i_k], for some set of indices 1 ≤ i₁ < i₂ < … < i_k ≤ |w|. A word w is k-subsequence universal over an alphabet Σ if every word in Σ^k appears in w as a subsequence. In this paper, we study the intersection between the set of k-subsequence universal words over some alphabet Σ and regular languages over Σ. We call a regular language L k-∃-subsequence universal if there exists a k-subsequence universal word in L, and k-∀-subsequence universal if every word of L is k-subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is k-∃-subsequence universal and, respectively, if it is k-∀-subsequence universal, for a given k. The algorithms are FPT w.r.t. the size of the input alphabet, and their run-time does not depend on k; they run in polynomial time in the number n of states of the input automaton when the size of the input alphabet is O(log n). Moreover, we show that the problem of deciding if a given regular language is k-∃-subsequence universal is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of k-subsequence universal words (paths) accepted by a given deterministic (respectively, nondeterministic) finite automaton, and ranking an input word (path) within the set of k-subsequence universal words accepted by a given finite automaton.