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.

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

Email this document to