Subword Balance in BinaryWords, Languages and Sequences

Issue title: New Frontiers in Scientific Discovery – Commemorating the Life and Work of Zdzislaw Pawlak

Article type: Research Article

Authors: Salomaa, Arto

Affiliations: Turku Centre for Computer Science, Joukahaisenkatu 3-5 B, 20520 Turku, Finland. E-mail: asalomaa@utu.fi

Abstract: 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 ω-words and periodicity. For the Fibonacci word, the D-values are in many ways connected with the Fibonacci numbers.

Keywords: subword, scattered subword, counting subwords, Parikh matrix, periodicity, Fibonacci word

Journal: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 469-482, 2007