Mathematics Colloquium
Date:Lincoln NE 68508
Affiliation: University of Waterloo
Local Host: David Pitts
Title: Decision procedures for problems in combinatorics on words
Additional Public Info:
Combinatorics on words is the study of (finite or infinite)
strings of symbols. A famous example of an infinite string is the
Thue-Morse word t = 0110100110010110…, in which the n’th term is
0 or 1 according to whether the sum of the digits of n, when expressed
in base 2, is even or odd. More than a hundred years ago, the Norwegian
mathematician Axel Thue famously proved that that t contains no
overlaps, that is, no blocks of the form AAa, where a is the first
letter of the block A. In this talk, I will discuss how results like
Thue’s can be proved purely mechanically, using a decision procedure.
Our Java implementation of this decision procedure has succeeded in proving many results from the literature, and also some new results.
Refreshments will be served in 348 Avery 3:30-4:00. The talk is free and open to the public.