2020/03/10 by Barker, Laura, Fleischmann, Pamela, Harwardt, Katharina +2 · 1 citation
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2003.04629
A word u=u1… un is a scattered factor of a word w if u can be obtained from w by deleting some of its letters: there exist the (potentially empty) words v0,v1,..,vn such that w = v0u1v1...unvn. The set of all scattered factors up to length k of a word is called its full k-spectrum. Firstly, we show an algorithm deciding whether the k-spectra for given k of two words are equal or not, running in optimal time. Secondly, we consider a notion of scattered-factors universality: the word w, with \letters(w)=Σ, is called k-universal if its k-spectrum includes all words of length k over the alphabet Σ; we extend this notion to k-circular universality. After a series of preliminary combinatorial results, we present an algorithm computing, for a given k'-universal word w the minimal i such that wi is k-universal for some k>k'. Several other connected problems~are~also~considered.