A note on word chains and regular languages (Q1115632)

Word chains have recently obtained some attention. We present a result that connects word chains to regular languages. Namely, we derive the inequality: \(\ell (L_{\leq n})/| L_{\leq n}| \leq 2+O(1/n),\) where \(L_{\leq n}\) denotes all words of length at most n that are members of an infinite regular language L, and \(\ell (L_{\leq n})\) is the length of a minimal word chain computing all \(w\in L_{\leq n}\). Finally, we show that even for two-letter alphabets there are words of length n that need \(\Omega\) (n/log n) steps to be computed using word chains.