Certain branches of mathematics constitute a major source of origin for formal language theory. The term mathematical language theory describes mathematical (algebraic) aspects of formal language theory - the main emphasis is on the mathematical theory rather than any applications. Hence our motivation comes from formal language theory and therefore the combinatorial aspect will be stressed more than algebraic aspect. Formal languages with special combinatorial and structural properties are exploited in information processing or information transmission[1].Moreover the theory has now developed into many directions and has generated a rapidly growing literature The theory
of words is profoundly connected to numerous different fields of mathematics and its applications. In this paper we extended some special combinatorial one dimensional word
properties to two dimensional arrays[3,4,5].
In section 2 we see some basic definitions. In section 3 we define Row (Column) Kolakoski array, Kolakoski array and we give some properties related to Kolakoski array. In addition to that we presented recursive formula for special nodes.
2 BASIC DEFINITIONS
Let Σ be a finite alphabet. The set of all words over Σ is denoted by Σ*. The empty word is denoted by l. We write Σ+ = Σ*- {l}.
An infinite word w over a finite alphabet Σ is a mapping from positive integers into Σ. We write w = a1 a2 ... ai ... where ai e £. The set of all infinite words over £ is denoted £ω. An infinite word w is ultimately periodic if w = uvw.
An infinite word w over a binary alphabet {a, b} which is not ultimately periodic and for any positive integer n, the number of its factors of length n, gx(n) = n + 1, is called a Sturmian word [2,3,4].The Fibonacci word f which is an important example of a Sturmian word is the fixed point of a morphism j : B* ® B* where B = {a,b} and j(a) = ab, j(b) = a i.e. f = jw(a). In fact the first few symbols of the Fibonacci word is abaababaabaababaababa …[4,5] .
An (mxn) array A = (aij) (mxn) over an alphabet Σ is a rectangular arrangement of symbols of Σ with m rows and n columns. The size of the array A is the ordered pair (mxn). The set of all arrays over Σ is denoted by Σ** . The empty array is also denoted by λ. We adopt the convention that for an (mxn) array A = (aij) (mxn) the bottom most row is the first row and the left most column is the first column. Also we write Σ++ = Σ** -{λ}. A factor or subarray of an array A is also an array which is a part of A (formed by deleting certain consecutive rows and certain consecutive columns of A).
An infinite array u has an infinite number of rows and infinite number of columns. The collection of all infinite arrays over Σ is denoted by Σωω.
Row and column concatenation of arrays in Σ** are partial operations. For row catenation of two arrays A and B , denoted by AqB, the number of columns in A and B should be equal and for column concatenation AfB of A and B, the number of rows in A and B should be equal. The collection of all arrays with finite number of rows and infinite number of columns is denoted by Σ *ω and the collection of all arrays with infinite number of rows and a finite number of columns is denoted by Σω*.
An array w e £ωω is said to be row ultimately periodic (Figure 1) if there exist two arrays u and v in Σ*ω such that w = uq vqΙ,where vqΙ denotes infinite number of row concatenation of v with v itself. An array w Σ ωω is said to be column ultimately periodic (Figure 2) if there exist two arrays u and v of Σω* such that
w = u f vfÉ, where vfÉ denotes infinite number of column concatenation of v with v itself.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
1
1
1
1
1
1
1
1
1
1 . . .
2
2
2
2
2
2
2
2
2
2
2
2 . . .
1
1
1
1
1
1
1
1
1
1
1
1 . . .
2
2
2
2
2
2
2
2
2
2
2
2 . . .
1
1
1
1
1
1
1
1
1
1
1
1 . . .
2
2
2
2
2
2
2
2
2
2
2
2 . . .
1
2
2
1
1
2
1
2
2
2
1
1 . . .
2
2
1
1
2
1
2
2
1
2
2
2 . . .
2
2
1
1
2
1
2
2
1
2
1
1 . . .
Figure 1
.
.
.
.
.
.
.
.
.
.
.
.
. . .
.
.
.
.
.
.
.
.
.
.
.
.
. . .
.
.
.
.
.
.
.
.
.
.
.
.
. . .
1
1
1
1
2
2
1
2
2
1
2
2
. . .
2
1
2
2
2
2
1
2
2
1
2
2
. . .
1
1
1
1
2
2
1
2
2
1
2
2
. . .
2
2
2
2
2
2
1
2
2
1
2
2
. . .
1
2
2
1
2
2
1
2
2
1
2
2
. . .
2
2
1
1
2
2
1
2
2
1
2
2
. . .
2
2
1
1
2
2
1
2
2
1
2
2
. . .
Figure 2
The famous Kolakoski wordε {1,2}w which consists of consecutive blocks of 1's and 2's such that the length of each block is either 1 or 2, and the length of the ith block is equal to the ith letter of . The word is an example of a self reading infinite word. = 221121221221121122121121. . . . . . . . . . . . is an example of a Kolakoski word [7].
3. KOLAKOSKI ARRAY
We define Row(Column) Kolakoski array and Kolakoski array and present some properties of Kolakoski array
DEFINITION:3.1
Let A= (aij) be an infinite array. The elements of A are called vertices of A. The vertex at the (i,i)th position is called as ith node of A. A path from an1 to a1n along the vertices an2an3…ann-1annan-1n… a2n is called right angle path. If all the vertices of right angle path are equal then the path is called layer of width 1.If two consecutive layers have same vertices then it is called a layer of width 2.
The Row (Column) Kolakoski array W consists of consecutive blocks of 1's and 2's such that in every row (column) the length of each block is either 1 or 2, and the length of the ith block in the jth row(column) is equal to (i,j)th vertex of W.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
2
1
1
2
1
2
2
1
2
.
.
1
2
2
1
1
2
1
2
2
2
.
.
2
2
1
1
2
1
2
2
1
2
.
.
1
2
2
1
1
2
1
2
2
2
.
.
1
2
2
1
1
2
1
2
2
2
.
.
2
2
1
1
2
1
2
2
1
2
.
.
2
2
1
1
2
1
2
2
1
2
.
.
Figure 1
Row Kolakoski array
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
2
1
1
2
1
2
.
.
.
.
.
1
1
2
2
1
2
1
.
.
.
.
.
2
2
1
1
2
1
2
.
.
.
.
.
1
1
1
1
1
1
1
.
.
.
.
.
1
1
2
2
1
2
1
.
.
.
.
.
2
2
2
2
2
2
2
.
.
.
.
.
2
2
1
1
2
1
2
.
.
.
.
.
Figure 2
Column Kolakoski array
The Kolakoski array W consists of consecutive layers of 1's and 2's such that the width of each layer is either 1 or 2, and the width of the ith layer is equal to the ith node of W. This is an example of a self reading infinite array. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
2
2
2
2
2
2
2
.
.
.
.
2
2
2
2
2
2
2
2
.
.
.
.
1
1
1
1
1
1
2
2
.
.
.
.
2
2
2
2
2
1
2
2
.
.
.
.
1
1
1
1
2
1
2
2
.
.
.
.
1
1
1
1
2
1
2
2
.
.
.
.
2
2
1
1
2
1
2
2
.
.
.
.
2
2
1
1
2
1
2
2
.
.
.
.
Figure 3
Kolakoski array
Remark :3.2
(i) Kolakoski array is a symmetric array.
(ii) The path joining the vertices along the main diagonal is a Kolakoski word.
(iii) The paths joining the vertices along right(left) diagonals and the preceding vertices in the first row(column) are Kolakoski words.
(iv) Kolakoski array is not ultimately periodic.
We seek more properties in this array which has many applications.
Let be Kolakoski array. The nth node is termed as special node and is denoted by Kn
We will now derive a recursive formula for Kn. Let
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Kn
2
2
1
1
2
1
2
2
1
2
2
1
1
2
1
1
kn
1
1
2
2
3
4
5
5
6
7
7
8
8
9
10
10
Table 1 : Kn and kn
Lemma 3.3
Proof: We first notice that
The left inequality holds by definition and the right one is valid, since if
we get a contradiction to the minimality of kn-1 . So, as the first case, we consider
which implies kn = kn-1 + 1 = . In the second case leads to .
We notice that Lemma 3.3 holds in general for every sequence, whose only values are 1 and 2
Lemma 3.4
Proof:
The following well known construction produces an array which is identical to Kolakosai array K. Start with Kk1 and corresponding layer twos, continue with Kk2 and corresponding layer ones, followed by Kk3 and corresponding layer twos and so on. In this construction, after kn-1 steps two cases can appear, as described in the proof of Lemma 3.2 The first possibility is that which means that we have constructed n-1 nodes of the array. Therefore, by construction Kn must be different from Kn-1 implying . In the second case that , it is necessary that , for if otherwise contradicting the miniality of kn-1. So our construction has added 2 equal numbers at the kn-1th step, such that Kn = Kn-1 and finally . The second equality follows by induction.
Corollary 3.5 is an implication of Lemma 3.4
Corollary 3.5
respectively.
Corollary 3.6 uses Lemma 3.3 and Corollary 3.5
Corollary 3.6
Corollary 3.7 follows from Corollary 3.6
Corollary 3.7
Hence we have
Theorem 3.8 For we have
5.CONCLUSION
In this paper we defined self reading infinite arrays and we investigate interesting properties Kolakoski arrays.
