Abstract:

A finite pattern (that is a string of symbols, aka a word) is avoidable on the n letter alphabet provided there is an infinitely long word on the n letter alphabet that, loosely speaking, has no instance (image) of the pattern as a subword. Patterns (i.e. words) which are not avoidable on any finite alphabet are said to be unavoidable. This talk is aimed at providing an algorithmic characterization of unavoidability. So this seminar continues the themes set out by Kate Scott over the earlier meetings of the seminar this semester.