Sökning: onr:"swepub:oai:research.chalmers.se:c9f9b779-56a5-45bf-ba4f-1ab02497afba" >
Finite automata and...
Finite automata and pattern avoidance in words
-
- Brändén, Petter, 1976- (författare)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematik,Department of Mathematical Sciences, Mathematics
-
- Mansour, Toufik, 1966 (författare)
- University of Haifa
-
(creator_code:org_t)
- Elsevier BV, 2005
- 2005
- Engelska.
-
Ingår i: Journal of Combinatorial Theory - Series A. - : Elsevier BV. - 1096-0899 .- 0097-3165. ; 110:1, s. 127-145
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://doi.org/10.1...
-
https://research.cha...
-
https://doi.org/10.1...
-
https://gup.ub.gu.se...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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 ⋯ (ℓ + 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. © 2004 Elsevier Inc. All rights reserved.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Nyckelord
- permutations
- permutations
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas