Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Finite automata and pattern avoidance in words
2005 (Engelska)Ingår i: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 110, nr 1, s. 127-145Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We say that a word w on a totally ordered alphabet avoids the word v if there are no subsequences in w order-equivalent to v. In this paper we suggest a new approach to the enumeration of words on at most k letters avoiding a given pattern. By studying an automaton which for fixed k generates the words avoiding a given pattern we derive several previously known results for these kind of problems, as well as many new. In particular, we give a simple proof of the formula (Electron. J. Combin. 5(1998) #R15) for exact asymptotics for the number of words on k letters of length n that avoids the pattern 12...(l + 1). Moreover, we give the first combinatorial proof of the exact formula (Enumeration of words with forbidden patterns, Ph.D. Thesis, University of Pennsylvania, 1998) for the number of words on k letters of length n avoiding a three letter permutation pattern.

Ort, förlag, år, upplaga, sidor
2005. Vol. 110, nr 1, s. 127-145
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:kth:diva-78741DOI: 10.1016/j.jcta.2004.10.007ISI: 000228439100008OAI: oai:DiVA.org:kth-78741DiVA, id: diva2:492831
Anmärkning
QC 20120227Tillgänglig från: 2012-02-08 Skapad: 2012-02-08 Senast uppdaterad: 2017-12-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltexthttp://dx.doi.org/10.1016/j.jcta.2004.10.007

Personposter BETA

Brändén, Petter

Sök vidare i DiVA

Av författaren/redaktören
Brändén, Petter
I samma tidskrift
Journal of combinatorial theory. Series A (Print)
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 13 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf