Factor Complexity and Abelian Complexity for Infinite Arrays
Authors :
Huldah Samuel a,* and V. Rajkumar Dareb
Author Address :
a,bDepartment of Mathematics, Madras Christian College, Tambaram, Chennai - 600 059.
*Corresponding author.
Abstract :
Combinatorics on words is an interesting area of research. For a given word, various complexity measures like factor complexity, abelian complexity, arithmetical complexity, palindromic complexity, permutation complexity etc have been defined in the literature. An infinite word can be defined as the limit of an increasing sequence of finite words. The problem of computing the complexity function p where p(n) is the number of distinct factors of length n of an infinite word was introduced in 1975 by Ehrenfeucht et al [3]. Abelian complexity of infinite words have been examined by Ethan M. Covan and Gustav A. Hedlund [1] and they have revealed that it could serve as an alternative way of characterisation of periodic words and Sturmian words. An infinite array over an alphabet is a rectangular arrangement of symbols in infinite rows and infinite columns. In this paper we define Thue-Morse array, and Variant Thue-Morse array. We also define the abelian complexity and factor complexity for infinite arrays such as Fibonacci array, Thue-Morse array, and Variant Thue-Morse array.
Keywords :
Mizoguchi-Takahashi contraction, fixed point theorem.
DOI :
Article Info :
Received : July 10, 2015; Accepted : August 23, 2015.
