A note on word chains and regular languages (Q1115632)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on word chains and regular languages |
scientific article |
Statements
A note on word chains and regular languages (English)
0 references
1989
0 references
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.
0 references
word chains
0 references
regular languages
0 references