Strict Bounds for Pattern Avoidance
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Francine Blanchet-Sadri, Professor (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
Abstract: Cassaigne conjectured in 1994 that any pattern with m distinct variables of length at least 3(2m-1) is avoidable over a binary alphabet, and any pattern with m distinct variables of length at least 2m is avoidable over a ternary alphabet. Building upon the work of Rampersad and the power series techniques of Bell and Goh, we obtain both of these suggested strict bounds. Similar bounds are also obtained for pattern avoidance in partial words, sequences where some characters are unknown.
Strict Bounds for Pattern Avoidance
PDF (Portable Document Format)
472 KB
Created on 6/27/2014
Views: 2590
Additional Information
- Publication
- Theoretical Computer Science, 506, 17-28
- Language: English
- Date: 2013
- Keywords
- Formal languages, Combinatorics on words, Pattern avoidance, Power series, Partial words