m-Nearly k-Universal Words -- Investigating Simon Congruence

Determining the index of the Simon congruence is a long outstanding open problem. Two words u and v are called Simon congruent if they have the same set of scattered factors, which are parts of the word in the correct order but not necessarily consecutive, e.g., mathttoath is a scattered factor of mathttlogarithm. Following the idea of scattered factor k-universality, we investigate m-nearly k-universality, i.e., words where m scattered factors of length k are absent, w.r.t. Simon congruence. We present a full characterisation as well as the index of the congruence for m=1. For mneq 1, we show some results if in addition w is (k-1)-universal as well as some further insights for different m.