# A context free language associated with interval maps.

For every interval map with finitely many periodic points of periods 1 and 2, we associate a word by taking the periods of these points from left to right. It is natural to ask which words arise in this manner. In this paper we give two different characterizations of the language obtained in this way.Keywords: interval map, periodic point, period

1 Introduction

A topological dynamical system is apair (X, f), where f is acontinuous self map on the topological space X. An element x [member of] X is called periodic if [f.sup.n](x)= x for some positive integer n and the least such n is called the f-period of x. Here we consider dynamical systems on the interval [0,1], which are generally called interval maps. For an interval map f with finitely many periodic points, say [x.sub.1] < [x.sub.2] < .... < [x.sub.n] we define w(f) = [p.sub.1][p.sub.2]...[p.sub.n], where pi is the f-period of [x.sub.i]. A known theorem of Sarkovskii[6] implies that each pi has to be a power of 2. A known fixed point theorem guarantees that one of the [p.sub.i]'s has to be 1 and infact, by a corollary of intermediate value theorem, it has to be in between the first 2 and the last 2 in this word (if at all there are 2's). If f and g are order conjugate then w(f) = w(g).

Now, it is natural to ask which words arise as w(f). The main objective of this paper is to answer the above question. Our main theorem is one about the location of fixed points vis a vis points of period 2 for interval maps. The results of this paper form the starting point of answering a grand question: Which dynamical systems arise as the restriction of interval maps f to the set of all f-periodic points?

2 Main Results

Let G be the collection of continuous self maps on I such that the periodic points of period 1 and 2 are finitely many. Let F be the sub collection of G consisting of all those maps for which all periodic points are of periods 1 or 2. We denote by [L.sub.p] (the language of periods) the set of all words w(f) where f [member of] F. This [L.sub.p] is a language over {1,2} and we seek a description of [L.sub.p]. Let L be the set of all words w(f) where f [member of] G. In this paper we prove that it coincides with [L.sub.p].

Some easy observations:

* The number of 2's has to be even in every word.

* If there is only one 1 in a word, then it has to be exactly in the middle.

* It is less obvious but true that the words like 222121 and 212212 are not in [L.sub.p].

Main theorem:

The following are equivalent for a word over {1,2}:

1. w [member of] [L.sub.p]. That is, there is an interval map f [member of] F such that w(f) = w.

2. w belongs to the smallest language, say [L.sub.g] satisfying:

([G.sub.1]) 1 [member of] [L.sub.g].

([G.sub.2]) u [member of] [L.sub.g] [??] {1u, u1, 2u2} [subset] [L.sub.g].

([G.sub.3]) {u, v} [subset] [L.sub.g] [??] u1v [member of] [L.sub.g].

Theorem 1 The language over {1,2} is context free, but the similarly defined language over {1, 2,4} is not context free.

3 A Context free language

To prove the main theorem, we introduce another language [L.sub.c], the set of words over {1, 2}, satisfying the condition below:

For w [member of] [L.sub.c], there exists a permutation [sigma] from {1,2,3,..., |w|}to itself (where |w| is the length of w) satisfying

([C.sub.1]) [sigma](i) = i if and only if [w.sub.i] = 1 ([w.sub.i] is the [i.sup.th] term of w).

([C.sub.2]) [sigma]([sigma](i)) = i [for all] i.

([C.sub.3]) If [sigma](i) < i and j < [sigma](j) then there exists a l between i and j such that [sigma] (l) = l. The map [sigma] in the above theorem is called a companion map; [sigma](i) is called the companion of i. Condition [C.sub.3] can be restated as follows: there should be a '1' between any two 2's whose companions are in opposite directions.

Lemma 1 If w [member of] [L.sub.c] then there exists a [??] : {1,2,..., |w|} [right arrow] {1, 2,..., |w|} satisfying [C.sub.1], [C.sub.2], [C.sub.3] and the following

[C.sub.4]: If i < j < [??](i) then i < [??](j) < [??](i) [for all]i, j [less than or equal to] |w|(this says that no two cycles are twined).

Proof: Let w [member of] [L.sub.c]. If [C.sub.4] fails, then there exist i, k such that i < k < [sigma](i) < [sigma](k); we say that [C.sub.4] fails at each of the four points. We also say that i and k form a twining

pair. Let i be the smallest point where [C.sub.4] fails and j be the largest point where [C.sub.4] fails. Then we call j - i as twining length. For the given word w, there may be many permutations satisfying [C.sub.1], [C.sub.2], [C.sub.3]. Choose [sigma] among them such that its twining length is minimal. Let [i.sub.1] > i be the smallest point forming a twining pair with i. Define [[sigma].sub.1] as [[sigma].sub.1]([i.sub.1]) = [sigma](i), [[sigma].sub.1](i) = [sigma]([i.sub.1]), [[sigma].sub.1.sup.2](i) = i, [[sigma].sub.1.sup.2]([i.sub.1]) = [i.sub.1], [[sigma].sub.1](k) = [sigma](k) [for all]k [not equal to] i,[i.sub.1],[sigma](i),[sigma]([i.sub.1]).

It is clear that [[sigma].sub.1] satisfies [C.sub.1], [C.sub.2] and [C.sub.3]. Thus, we have removed the twining in the first pair of twining cycles. Repeat the process to define [[sigma].sub.2],[[sigma].sub.3],..., [[sigma].sub.k], each time removing one twining at i, until the condition [[sigma].sub.k](i) > [sigma](l) for every i < l < [[sigma]k](i) is satisfied for some k [member of] N. Since at every stage, the image of i is increasing and |w| is finite, this shall take only a finite number of steps. In this way we get [??] such that its twining length is less than j - i, which contradicts the minimality of twining length. Therefore for every w [member of] [L.sub.c] there exists a [??] satisfying [C.sub.4].

Lemma 2 u [member of] [L.sub.p] if and only if u1, 1u [member of] [L.sub.p].

Proof: Let u [member of] [L.sub.p]. Then there exists a continuous function g : [0,1] [right arrow] [0,1] such that w(g) = u. Define f : [0,1] [right arrow] [0,1] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In other words f is the transfer of g on [0, 1/2], f(1/2) = g(1)/2, f(3/4) = 5/8, f(1) = 1, and f is linearly extended elsewhere.

P(f) = {x/2|x [member of] P(g)} [union] {1}. Graph of f is below the diagonal in (1/2, 1) and [0, 1/2] is invariant.

Therefore there is no periodic point strictly between 1/2 and 1. w(f) = u1. Therefore u1 [member of] [L.sub.p]. Similarly we can prove that 1u [member of] [L.sub.p].

In fact we prove that if either 1u [member of][L.sub.p] or u1 [member of][L.sub.p] then u [member of] [L.sub.p]. Let u1 [member of] [L.sub.p]. Then there exists a function f : [0,1] [right arrow] [0,1] such that w(f) = u1. Let [x.sub.1] < [x.sub.2] < ... < [x.sub.n] be the periodic points of f and it is clear that f([x.sub.n]) = [x.sub.n].

Define g : [0,1] [right arrow] [0,1] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then P(g) = {[x.sub.1],[x.sub.2], ...[x.sub.n-1]} and w(g) = u. Therefore u [member of] [L.sub.p]. Similarly we can prove that if 1u [member of] [L.sub.p] then u [member of] [L.sub.p].

Lemma 3 If u [member of] [L.sub.p] then 2u2 [member of] [L.sub.p].

Proof: Let g : [0,1] [right arrow] [0,1] be a continuous function such that w(g) = u. Define f : [0,1] [right arrow] [0,1] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(In other words, f is the transfer of g on [1/4, 1/2], f(0) = 1, f(1/4) = (1/4)(g(0)+1), f(1/2) = (g(1)+1/4), f(3/4) = g(1)+1/16, f(1) =0, and f is linearly extended elsewhere.)

P(f) = {x/4 + 1/4|x [member of] P(g)} [union] {0,1}.

Choose q in the last lap such that f(q) = 1/4. Then choose p in the first lap such that f(p) = q. Then f takes [q, 1] to [0, 1/2]. Therefore f [??] f is monotonic on [0,p] and [q, 1]. If p < x < 1/4, then f [??] f(x) [member of] [1/4, 1/2]. The interval [1/4, 1/2] is invariant, and so x is not periodic. If 1/2 < x < 1, then f(x) [member of] [1/4, 1/2] and so x is not periodic. Therefore w(f) = 2u2. Thus 2u2 [member of] [L.sub.p].

Remark 1 The converse of the above lemma is not true. 221221212 [member of] [L.sub.p] but 2122121 [??] [L.sub.p].

Lemma 4 If u, v [member of] [L.sub.p] then u1v [member of] [L.sub.p].

Proof: Let u,v [member of] [L.sub.p] then by Lemma 2, u1, 1v [member of] [L.sub.p]. Then there exists continuous functions g : [0,1] [right arrow] [0,1], h : [0,1] [right arrow] [0,1] and g(1) = 1, h(0) = 0 such that w(g) = u1, w(h) = 1v,. Define f : I [right arrow] I by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

P(f) = {x/2|x [member of] P(g)} [union] {x+1/2|x [member of] P(h)}. Therefore w(f) = u1v.

Remark 2 The converse of the above lemma is not true. 22122 [member of] [L.sub.p] but 22 [??] [L.sub.p]

While constructing the proofs of the above three lemmas 2,3,4, we have introduced piecewise linear segments in such a way that the slopes 1,-1,0 are avoided.

Examples:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [ILLUSTRATION OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [ILLUSTRATION OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [ILLUSTRATION OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [ILLUSTRATION OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [ILLUSTRATION OMITTED]

Theorem 2 [L.sub.p] = [L.sub.g].

Proof: Step 1: First we prove [L.sub.p] [subset] [L.sub.g].

To prove this, we consider the language [L.sub.c] introduced in the beginning of Section 3 and prove that [L.sub.p] [subset] [L.sub.c] [subset] [L.sub.g]. Let w [member of] [L.sub.p], then there is an interval map f such that w(f) = w. Then [x.sub.i] and f([x.sub.i]) are companions to each other, for every periodic point [x.sub.i]. Define [sigma] : {1,2,.., |w|}[right arrow]{1,2,.., |w|} by [sigma](i) = j if f([x.sub.i]) = [x.sub.j]. It is easy to observe that [C.sub.1] and [C.sub.2] are satisfied. Now we prove that [C.sub.3] is satisfied.

If [sigma](i) < i < j < [sigma](j), then f([x.sub.i]) < [x.sub.i] < [x.sub.j] < f([x.sub.j]). By Intermediate value theorem there is a fixed point between [x.sub.i] and [x.sub.j]. So there is a 1 between [w.sub.i] and [w.sub.j]. Similarly, if i > [sigma](i) > [sigma](j) > j or i > [sigma](j) > [sigma](i) > j or i > [sigma](j) > [sigma](i) > j or i > [sigma](j) > j > [sigma](i), there is a fixed point between i,j. Therefore [C.sub.3] is satisfied and sow [member of] [L.sub.c]. Therefore [L.sub.p] [subset] [L.sub.c].

Now we prove that [L.sub.c] [subset] [L.sub.g]. Suppose it is not true.

Let w [member of] [L.sub.c] be the word of smallest length, which is not in [L.sub.g]. Then there exists a[sigma]:{1,2,...,|w|}[right arrow] {1,2,..., |w|} such that the conditions [C.sub.1], [C.sub.2], [C.sub.3] and [C.sub.4] are satisfied (by Lemma 1). It is clear from the definition of [L.sub.c] that w [member of] 1Lc if [sigma](1) = 1, w [member of] [L.sub.c]1 if [sigma](|w|) = |w|, w [member of] 2[L.sub.c]2 if [sigma](1) = [sigma](|w|) and w [member of] [L.sub.c]1[L.sub.c] if 1 < [sigma](1) < [sigma](|w|) < |w|. That means there exists u [member of] [L.sub.c] such that w = 1u or u1 or 2u2 or u1v (where v [member of] [L.sub.c]). By the minimality of length of w, we have that u,v [member of] [L.sub.g]. Therefore w [member of] [L.sub.g], a contradiction. Hence [L.sub.c] [subset] [L.sub.g]. This implies that [L.sub.p] [subset] [L.sub.g].

Step 2: [L.sub.g] [subset] [L.sub.p].

This inclusion follows from Lemma 2, 3 and 4. Therefore [L.sub.g] [subset] [L.sub.p].

Remark 3 Theorem 1 completely describes the location of fixed points between the points of period 2. For f [member of] G, we define w{1,2}(f) as [p.sub.1][p.sub.2]...[p.sub.n], where [p.sub.1],[p.sub.2], ..[p.sub.n] are the f-periods of the fixed points of f [??] f, say [x.sub.1] < [x.sub.2] < ... < [x.sub.n]. Then we get anew language L = {w{1,2}|f [member of] G} and obviously [L.sub.p] [subset] L. In fact, the following theorem says that L = [L.sub.p].

Theorem 3 L = [L.sub.p].

Proof: It is obvious that [L.sub.p] [subset] L and now we prove that L [subset] [L.sub.p]. To prove this we recall [L.sub.c] and prove that L [subset] [L.sub.c], since [L.sub.p] = [L.sub.c]. Let w [member of] L and let f [member of] G be such that w = [w.sub.{1,2}](f). Define [sigma] : {1,2,.., |w|} [right arrow] {1, 2,.., |w|} by [sigma](i) = j if f([x.sub.i]) = [x.sub.j]. It is easy to observe that [C.sub.1] and [C.sub.2] are satisfied. Now we will prove that [C.sub.3] is satisfied.

If [sigma](i) < i < j < [sigma](j), then f([x.sub.i]) < [x.sub.i] < [x.sub.j] < f([x.sub.j]). By the Intermediate value theorem, there is a fixed point between [x.sub.i] and [x.sub.j]. So there is a 1 between [w.sub.i] and [w.sub.j]. Therefore [C.sub.3] is satisfied and so w [member of] [L.sub.c]. Therefore L [subset] [L.sub.c].

Remark 4 From the above theorem we can observe:

* If w [member of] L, the new word obtained by inserting any number of 1's, anywhere in w, will also be in L. Here is a description of all words with six 2's: the three words 2221222, 212122122, 221221212 and all words by insertion of additional 1's any where. There are no other words in L with exactly six 2's.

* Here we give the list of all words in L whose length is less than 7.

1

11

111, 212

1111, 1212, 2121, 2112

11111, 11212, 12121, 12112, 21211, 21121, 21112, 22122

111111, 212111, 211211, 211121, 211112, 121211, 121121, 121112, 112121, 112112, 111212, 122122, 212122, 221122, 221221.

Remark 5 For w = [w.sub.1][w.sub.2]...[w.sub.n] [member of] L, there exists an interval map f such that w(f) = w. Let [x.sub.1] < [x.sub.2] < ... < [x.sub.n] be the periodic points of f and [w.sub.i] be the period of [x.sub.i]. Now we define that [w.sub.i] is equal to * when f([x.sub.i]) = [x.sub.i], to [when [x.sub.i] < f([x.sub.i]) and to ] when f([x.sub.i]) < [x.sub.i]. Note that w(f) is a well-formed parentheses word as every ] to the right is in correspondence with a [ to the left and it is well known that well-parentheses words are exactly those with as many [ as ] and such that every prefix has at least as much [ as ]. Consider any i < j such that [w.sub.i] and [w.sub.j] are different kinds of parentheses, either [x.sub.i] < f([x.sub.i]) and f([x.sub.j]) < [x.sub.j] or f([x.sub.i]) < [x.sub.i] and [x.sub.j] < f([x.sub.j]) thus by the intermediate value theorem f admits a fixed point in the interval [[x.sub.i], [x.sub.j]], i.e., there is a * somewhere in between every pair of different parentheses in w(f), or equivalently the word w(f) cannot contain the factor [] nor the factor ][. To summarize, we have proven that w(f) is included in the language defined by the following grammar: S[right arrow]*|[S]|S * S|* S|S*. To prove that every word in the language can be produced, one can easily proceed by induction using piecewise linear functions (f(x) = x/2 realizes the * and lemmas 2, 3 and 4 in the paper give short explicit constructions of the inductive steps). The language L is the projection of this language, that is the language with the following grammar: S[right arrow]1|2S2|S1S|1S|S1.[.sub.(i)]

L is a context free language with the grammar defined above.

Remark 6 Using the pumping lemma for regular languages[5], we can prove that this language is not regular.

Remark 7 It can be proved that, for every word w [member of] [L.sub.p], there is a piecewise linear map f such that every critical point of f is a periodic point (the proofs of our lemmas can be modified to yield this). This f is post critically finite[2]. From Thurston's theorem([2]) for real polynomials there exists only one polynomial p up to affine conjugation with the same kneading data as f. Here we have the open question: Is w(p) the same as w(f)?

Remark 8 The main result of this paper leads us to the question: What are all the finite subsystems f|P(f), if f [member of] F ? This question can be restated as follows: Given a word from the above language L, what are all the "pairings of 2's" that are allowed for interval maps?

4 A Language that is not context free

Let C be the class of interval maps f such that P(f) is finite. For f [member of] C, let [x.sub.1] < [x.sub.2] < ... < [x.sub.n] be the periodic points of f, whose period is in A. We denote [w.sub.A](f) by [w.sub.1][w.sub.2]..[w.sub.n], where [w.sub.i] [member of] A is the f-period of [x.sub.i] for 1 [less than or equal to] i [less than or equal to] n and [L.sub.A] denote the collection of all words [w.sub.A](f) over A, where f [member of] C. For [w.sub.j] [member of] N, [w.sub.j.sup.k] means [w.sub.j][w.sub.j]...[w.sub.j] (k times). For f [member of] [C.sup.0](I), P is a periodic orbit of period [2.sup.n]. We say P is simple if for any subset {[x.sub.1], [x.sub.2],..., [x.sub.k]} of P where k [greater than or equal to] 2 divides [2.sup.n], for any positive integer r which divides [2.sup.n], such that {[x.sub.1], [x.sub.2],..., [x.sub.k]} is periodic orbit of [f.sup.r] with [x.sub.1] < [x.sub.2] < ... < [x.sub.k], we have

[f.sup.r]({[x.sub.1],[x.sub.2],...,[x.sub.k/2]}) = {[x.sub.k/2+1],...,[x.sub.k]}.

Theorem 4 [4] Let f [member of] C(I) and suppose that f has a simple periodic orbit of period [2.sup.n]. Then there exists n + 1 simple periodic orbits of periods 1,2,4,..., [2.sup.n] such that the [2.sup.k] periodic points of period [2.sup.k] are separated by the 1 + 2 + ... + [2.sup.k-1] = [2.sup.k] - 1 fixed points of [f.sub.2.sub.k-1] for any k = 1,2,..., n.

Theorem 5 [4.sup.n][24.sup.n][14.sup.n][24.sup.n] [member of] [L.sub.{1,2,4}]

Proof: [2.sup.n] [12.sub.n] [member of] [L.sub.p], then there exists a function f [member of] F on [0,1] such that w(f) = [2.sub.n] [12.sub.n]. Define [??] : [0, 3] [right arrow] [0,3] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In [1, 2], its graph is a line joining (1, f(1)), (2,0) and ([??])|[.sub.[0,1]] = f|[.sub.[0,1]], P([??]) = P(f)[union]{x+2|x [member of] P(f)} [union] { a fixed point in [1, 2]}. Therefore [w.sub.{1,2,4}](f) = [4.sup.n][24.sup.n][14.sup.n][24.sup.n].

Theorem 6 If [4.sup.n.sub.1][24.sup.n.sub.2][14.sup.n.sub.3][24.sup.n.sub.4] [member of] [L.sub.{1,2,4}] if and only if [n.sub.1] = [n.sub.2] = [n.sub.3] = [n.sub.4].

Proof: Let [4.sup.n.sub.1][24.sup.n.sub.2][14.sup.n.sub.3][24.sup.n.sub.4] [member of] [L.sub.{1,2,4}], then there exists a function f [member of] C such that [w.sub.A](f) = [4.sup.n.sub.1][24.sup.n.sub.2][14.sup.n.sub.3][24.sup.n.sub.4] (since f has finitely many periodic points, according to a theorem of Block[1]). Every 4-cycle has to be separated by a 2-cycle and a 1-cycle. In every 4-cycle between any two points, a point of period 1 or 2 should be present. Here there are four blocks of 4's of length [n.sub.1], [n.sub.2], [n.sub.3], [n.sub.4]. From Theorem 4 it follows that every 4-cycle meets each block once and only once. So the size of each block is the same. Therefore [n.sub.1] = [n.sub.2] = [n.sub.3] = [n.sub.4].

Theorem 7 [L.sub.{1,2,4}] is not a context free language.

Proof: This follows from Theorem 5, Theorem 6 and pumping lemma[5] for context free languages.

References

[1] Louis Block, Simple periodic orbits of mappings of the interval, Trans. Amer. Math. Soc. 254, 391-398, 1979.

[2] Bodil Branner and Poul Hjorth, Real and Complex Dynamical Systems, Springer Science and Business Media, 464, 2013.

[3] Saber N Elaydi, Discrete Chaos: With Applications in Science and Engineering, CRC Press, 2007.

[4] Jaume Llibre and Agusti Reventos, On the structure of the set of periodic points of a continuous map of the interval with finitely many periodic points, Arch. Math. (Basel), 39, 331-334, 1982.

[5] K. L. P. Mishra and N. Chandrasekaran, Theory of Computer Science Automata, Languages and Computation, 3rd edition. Prentice-Hall of India, New Delhi, 2007.

[6] A.N Sarkovskii. [1964] : Coexistence of cycles of continuous mapping of the line into itself. Ukrainian Math. J., 16, 61-71 [in Russian]; [1995] : Intern. J. Bifurcation and Chaos 5, no. 5, 1263-1273.

M. Archana (*)

University of Hyderabad, India

received 1st Oct. 2014, revised 24th Apr. 2016, 20th June 2016, accepted 6th Aug. 2016.

(*) I am fully supported by UGC, India.

(i) We are thankful to the referee for suggesting this remark and for avoiding our inclusion of a proof of another characterization of L.

Printer friendly Cite/link Email Feedback | |

Author: | Archana, M.; Kannan, V. |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Date: | Nov 1, 2016 |

Words: | 4159 |

Previous Article: | Sequential selection of the [kappa] best out of n rankable objects. |

Topics: |