<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
1-17 Algorithms for Producing and Ordering Lexical and Nonlexical Sequences out of One Element
Elias Abboud
Beit Berl College, Doar Beit Berl, 44905 Israel
Annals of Combinatorics 15 (1) pp.1-17 January, 2011
AMS Subject Classification: 05A17, 68R15, 37B10
This paper deals with algorithms for producing and ordering lexical and nonlexical sequences of a given degree. The notion of “ “elementary operations”” on positive a-sequences is introduced. Our main theorem answers the question of when two lexical sequences are adjacent. Given any lexical sequence, α∈Ln; we can produce its adjacent successor as follows; apply one elementary operation on the tail of the longest left sequence, of even length, which gives a lexical successor α'∈Ln, then compute the fundamental sequence f = α ^ α'∈Lm and conclude for m n that a is adjacent to α' in Ln; ; . Whereas for m | n, the sequence α is adjacent to a sequence generated by f and the least element of Ld; where d = : Thus, while right sequences control the lexicality property of an α-sequence, it turns out that left sequences
control the adjacency property of lexical and nonlexical sequences.
Keywords: elementary operations, splitting of a cell, conjugation of a cell, lexical sequences, adjacent


1. Bivins, R.L., Louck, J.D., Metropolis, N., Stein, M.L.: Classification of all cycles of the parabolic map. Phys. D 51(1-3), 3--–27 (1991)

2. Brucks, K.M.: MSS sequences, coloring of necklaces and periodic points of f (z)= z2-2. Adv. Appl. Math. 8(4), 434--–445 (1987)

3. Chen, W.Y.C., Louck, J.D., Wang, J.: Adjacency and parity relations of words in discrete dynamical systems. J. combin. Theory Ser. A 91(1-2), 476--–508 (2000)

4. Dai, W.J., L¨u, K.B., Wang, K.B.: Combinatorics on words in symbolic dynamics: the quadratic map. Acta Math. Sin. (Engl. Ser.) 24(12), 1985--–1994 (2008))

5. Hao, B.L., Zheng, W.M.: Applied Symbolic Dynamics and Chaos. World Scientfic Publishing Co. Pte. Ltd., Singapore (1998)

6. Louck, J.D.: Problems in combinatorics on words originating from discrete dynamical systems. Ann. Combin. 1(1), 99–--104 (1997)

7. Louck, J.D., Metropolis, N.: Symbolic Dynamics of Trapezodial Maps. Reidel, Dordrecht (1986)

8. Louck, J.D., Stein, M.L.: Relations between words and maps of the interval. Ann. Combin. 5(3-4), 425–--449 (2001))

9. Sun, L., Helmberg, G.: Maximal words connected with unimodal maps. Order 4(4), 351–-- 380 (1987)