2021/04/19 by Pamela Fleischmann, Fleischmann, Pamela, Sebastian Bernhard Germann +3 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #DNA and Biological Computing #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.2104.09063
Scattered factor (circular) universality was firstly introduced by Barker et al. in 2020. A word w is called k-universal for some natural number k, if every word of length k of w's alphabet occurs as a scattered factor in w; it is called circular k-universal if a conjugate of w is k-universal. Here, a word u=u1⋯ un is called a scattered factor of w if u is obtained from w by deleting parts of w, i.e. there exists (possibly empty) words v1,…,vn+1 with w=v1u1v2⋯ vnunvn+1. In this work, we prove two problems, left open in the aforementioned paper, namely a generalisation of one of their main theorems to arbitrary alphabets and a slight modification of another theorem such that we characterise the circular universality by the universality. On the way, we present deep insights into the behaviour of the remainder of the so called arch factorisation by Hebrard when repetitions of words are considered.