Exponential lower bounds for the number of words of uniform length avoiding a pattern

Exponential lower bounds for the number of words of uniform length avoiding a pattern

12 Pages · 2007 · 152 KB · English

Theoret. Comput. Sci., 339 (1) (2005), pp. 7-18. [7]. J. Karhumäki, J. ShallitPolynomial versus exponential growth in repetition-free binary words. J. Comb. Theory Ser. A, 105 (2) (2004), pp. 335-347. [8]: M. Lothaire, Algebraic combinatorics on words, in: Encyclopedia of Mathematics and its Appli

Exponential lower bounds for the number of words of uniform length avoiding a pattern free download

Information and Computation 205 (2007) 1295–1306 wwwelseviercom/locate/ic Exponential lower bounds for the number of words of uniform length avoiding a pattern Jason P Bell a,∗ , Teow Lim Goh b aDepartment of Mathematics, Simon Fraser University, 8888 University Dr, Burnaby, BC, Canada V5A 1S6 bDepartment of Mathematics, University of Michigan, East Hall, 525 East University Ave, Ann Arbor, MI 481091109, USA Received 16 May 2005; revised 8 January 2007 Available online 28 February 2007 Abstract We study words on a finite alphabet avoiding a finite collection of patterns Given a patternpin which every letter that occurs inpoccurs at least twice, we show that the number of words of lengthnon a finite alphabet that avoidpgrows expo nentially withnas long as the alphabet has at least four letters Moreover, we give lower bounds describing this exponential growth in terms of the size of the alphabet and the number of letters occurring inp We also obtain analogous results for the number of words avoiding a finite collection of patterns We conclude by giving some questions © 2007 Elsevier Inc All rights reserved Keywords:Pattern avoidance; Combinatorics on words; Avoidable patterns 1 Introduction LetXbe a finite alphabet and letpbe a word on some other alphabetY We say that a word inXavoids the patternpif it contains no subword of the formh(p), wherehis a nonerasing homomorphism from the free monoidY ∗generated byYto the free monoidX ∗generated byX We say thatpisavoidable onXif there are infinitely many words that avoid the patternp We say that a patternpisavoidableif it is avoidable on some finite alphabet The Zimin algorithm [8, Section 32] is a recursive algorithm that determines if a given pattern is avoidable or unavoidable Given a patternpon an alphabetY, we define S(p,X)={h(p)|h:Y ∗→X ∗is a nonerasing homomorphism}(11) We say that a wordWon the alphabetXisof the formpifW∈S(p,X) The study of pattern avoidance began in the early 1900s with Thue’s work on squarefree words [14, 15] (see also Nagell et al [11]) A word on a finite alphabetXissquarefreeif it contains no subword of the formww, where wis a nonempty word onX Equivalently, a word is squarefree if it avoids the patternt 2 Squarefree words have seen numerous applications over the years In group theory, they have been used in giving a counterexample ∗Corresponding author Email addresses:[email protected] (JP Bell), [email protected] (TL Goh) 08905401/$ see front matter © 2007 Elsevier Inc All rights reserved doi:101016/jic200702004 1296JP Bell, TL Goh / Information and Computation 205 (2007) 1295–1306 to the unrestricted Burnside problem [1] An interesting application to unending chess appears in Morse and Hedlund [10] Much work has been done on counting squarefree words over various alphabets [3, 12] More gen erally, one can look at words that avoid the patternt jfor somej  2 Work on this problem has been done by Brandenburg [4] and Bean et al [2] An excellent survey of pattern avoidance is found in Chapter 3 of Lothaire [8] In addition to this, Currie [5, 6] has given many interesting open problems on the topic of pattern avoidance We note that ifa(n)denotes the number of words of lengthnon an alphabetXwhich avoid some pattern or collection of patterns, thena(n)issubmultiplicative; that is,a(n+m)  a(n)a(m) Sincea(n)is a submultiplica tive sequence of natural numbers, Fekete’s lemma (cf Madras and Slade [9, Lemma 122]) shows that lim n→∞ a(n) 1/n exists and is equal to some nonnegative real number When this limit is greater than 1, the number of words a(n)of lengthnthat avoid our given collection of patterns grows exponentially In this paper, we show that for a large class of avoidable patterns, this exponential growth phenomenon occurs Specifically, we look at patternspon some finite alphabet with the property that every letter in the alphabet occurs at least twice inp Such patterns are known to be avoidable [8, Cor 3210] We are able to give exponential lower bounds and thus obtain a stronger result Theorem 1Letpbe a pattern onk  2letters in which every symbol occurs at least twiceThen form  4and (k,m)=(2, 4)there are at least(k,m) nwords of lengthnon anmletter alphabet that avoidp,where (k,m):=m 1+1 (m−2) k −1 (12) We note that

------------- Read More -------------

Download exponential-lower-bounds-for-the-number-of-words-of-uniform-length-avoiding-a-pattern.pdf

Exponential lower bounds for the number of words of uniform length avoiding a pattern related documents

Habiting Space and the Representational Limits of Latour's Semiotics of Assemblies.

18 Pages · 2002 · 1.06 MB · English

mantles 81 underclothing. On the top of . The favourite type of Australian house is laid out in an oblong block bisected by Furthermore, items such as the hair trunk map Elliott's present life in Australia to the one he . reading with the semantic exhaustion of a given place: 'The reading of space

The Messenger Newsletter

8 Pages · 2016 · 1.13 MB · English

Even a “quiet” restaurant or the “sanctuary” of a. Sunday morning Prayer, Conversing with God, describes prayer not as a one-way very quietly. Elijah heard God not as a mighty wind, not Please see Lone Tree Point, page 5 

User-Friendly Ontology Editing and Visualization Tools: The

6 Pages · 2009 · 588 KB · English

User-friendly ontology editing and visualization tools: the OWLeasyViz approach Nadia Catenazzi, Lorenzo Sommaruga, Riccardo Mazza Semantic and Multimedia Systems Lab

A review of the literature regarding stress among nursing students during their clinical education

11 Pages · 2014 · 212 KB · English

Background: There has been increased attention in the literature about stress among nursing students. It has Keywords: Clinical Practice, Literature Review, Nursing Students, Stress, Nursing Education, Clinical Education, McKenna, L. & Plummer, V. (2013) Indonesian student nurses' perceptions.

In re Marriage of Bloom 2014 IL App (2d) 130642

8 Pages · 2014 · 39 KB · English

Respondent, Michelle Bloom, appeals an order of the circuit court of Du Page County imposing sanctions against . Respondent contends that our decision in In re Marriage of Bloom, 2013 IL App. (2d) 1210863-U, somehow . She cites In re Marriage of Yakin, 107 Ill. App. 3d 1103, 1120. (1982), for the 

1 In the Footsteps of Giants My Itinerary from Glasgow to Princeton

38 Pages · 2004 · 1.17 MB · English

barefoot and were therefore considered unsuitable playmates for her. My mother . of triumph, encouragement or disapproval from the huge combative crowds, then made A stranger in a new land, I had been immediately made.

Chef Solus and the Explorers Introduce The Food Groups

1 Pages · 2009 · 970 KB · English

Chef Solus and the Explorers Introduce The Food Groups Visit www.ChefSolus.com for printable worksheets for kids, nutrition education games, puzzles, activities and more!

A Solution to Unproductive Conversations

3 Pages · 2009 · 498 KB · English

first taking place. The effectiveness and efficiency of executive ladder and have not developed the communications skills needed for executive positions. executives to act in concert and to chart a winning course. We often hear 

Proteomics and Protein Analyses of Ovine and Caprine Body Fluids

11 Pages · 2014 · 890 KB · English

1Department of Veterinary Public Health, Faculty of Veterinary Medicine, Agricultural University of Tirana, Albania; Although the proteomes of body fluids have been described in detail for some animal species, there are few equivalent . by the identification and application of specific protein bio

a new christ

126 Pages · 2006 · 1.34 MB · English

PART 3: A NEW WORLD IN THE MAKING by Henry Drummond. The Greatest Thing in the World. 79 .. perfection. We are awed and shaken by its magnitude. It is . of blessings, spiritual, mental and physical. There is an old saying,.