×

Subword balance in binary words, languages and sequences. (English) Zbl 1108.68072

Summary: We investigate binary words and languages having a balanced structure of scattered) subwords. We introduce a “difference function” \(D\) for binary words. For \(D=0\), the resulting language is properly context-sensitive. Parikh matrices constitute a useful technical tool in the study, we investigate also the independence of their entries. The investigation is extended to concern \(\omega\)-words and periodicity. For the Fibonacci word, the \(D\)-values are in many ways connected with the Fibonacci numbers.

MSC:

68Q45 Formal languages and automata
68R15 Combinatorics on words
PDFBibTeX XMLCite