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

DEPARTMENT of HEALTH and HUMAN - Centers for Disease Control and

507 Pages · 2008 · 6.61 MB · English

influenza, natural disasters, and terrorism, while remaining focused on the threats to health and local, tribal and territorial health network.

A Typology of Victim Characterization in Television Crime Dramas

33 Pages · 2010 · 278 KB · English

her analysis of one season of Law & Order, NYPD Blue, and The Practice. She found that only

Immigration and Economy in the Globalization Process

236 Pages · 2002 · 1.63 MB · English

will need employees with the right skills and motivation. Switching to an active im- Finland by analyzing the development of the volume of foreign-born and foreign na- tionals and direct foreign . In the globalization trend of corporations, competition has shifted from natural re- source and expen

International Student Guide for Employment in the US

19 Pages · 2012 · 741 KB · English

Problem- If you do not speak English as a native language, you are at a distinct disadvantage communicating with recruiters. Solution- Consciously make an effort to talk with Americans: • Make presentations, take English courses, and work tirelessly at improving your English skills. • Ask a fel

Binders for radioactive waste forms made from pretreated calcined sodium bearing waste

8 Pages · 2006 · 187 KB ·

Although calcination of the pretreated SBW produces a instance metakaolin mixed with NaOH proved to be a superior binder for solidification.

List of Developing Nations Afghanistan Albania Algeria Angola

2 Pages · 2011 · 538 KB ·

Algeria. Angola. Antigua and Barbuda. Argentina. Armenia. Azerbaijan Hungary. India. Indonesia. Iran, Islamic Republic of. Iraq. Jamaica. Jordan.

22 NAVAJO NATION COUNCIL | Office of the Speaker

2 Pages · 2013 · 295 KB · English

Law and Order Committee receives update regarding and an additional amount of $1.4 million to ensure operation through operations through the winter season.

The European Car Parking Sector Sees M&A Flurry, But Will It Be An Easy Ride For Investors?

11 Pages · 2017 · 813 KB · English

The European Car Parking Sector Sees M&A Flurry, But Will It Be An Easy Ride For Investors? spglobal.com/ratingsdirect. Dec. 6, 2017. 2. Despite lots of M&A activity in the. European car parking sector, the future is somewhat uncertain. Acquisitions are the major growth catalyst for operators, but

Building Permits Granted Development Services Department City of San Antonio

84 Pages · 2012 · 272 KB · English

438 RICHLAND HILLS DR BLDG 10. DL CAMBRIDGE DEV GROUP, INC. (713)961-1336 x. 2251200. NEW 2-STORY MULTI-FAMILY APARTMEN. $947,363.00 2284202. 20x4=80 sq ft at csw, 171 sq ft at approach. $0.00. 3106 PIEDRA DE RIO. PRESIDIO CONST LLC. (210)679-8837 x. 2284203.

Department of History Postgraduate Handbook 2017-18

48 Pages · 2017 · 906 KB · English

Social and cultural change in early modern Ireland; the diffusion of print and the changing experience of . support for their modules (https://www.maynoothuniversity.ie/current-students). Social Media. The Department of History has a presence on social Format (e.g., film, video, DVD), that is, the