Properties Related To Kolakoski Array Biology Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

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.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.