Back to Search
Start Over
Finite automata and pattern avoidance in words
- Source :
-
Journal of Combinatorial Theory - Series A . Apr2005, Vol. 110 Issue 1, p127-145. 19p. - Publication Year :
- 2005
-
Abstract
- Abstract: We say that a word w on a totally ordered alphabet avoids the word if there are no subsequences in w order-equivalent to . 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 . 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. [Copyright &y& Elsevier]
- Subjects :
- *AUTOMATION
*UNIVERSITIES & colleges
*SEQUENTIAL machine theory
*ELECTRONS
Subjects
Details
- Language :
- English
- ISSN :
- 00973165
- Volume :
- 110
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series A
- Publication Type :
- Academic Journal
- Accession number :
- 17613928
- Full Text :
- https://doi.org/10.1016/j.jcta.2004.10.007