Christopher Hawthorne, Department of Pure Mathematics, University of Waterloo
"F-automatic sets"
Given a set of natural numbers A, is the set of base p representations of elements of A a regular language over {0,...,p-1}? In other words, given a string of digits base p, can we check whether it represents an element of A using a bounded amount of memory? The sets for which the answer is "yes" are called the p-automatic sets, and are an important object in the study of formal languages. In this talk, we will see that this notion can be generalized to subsets A of certain abelian groups Γ, with an injective endomorphism F : Γ -> Γ taking the role of p; we call these F-automatic sets. We will consider the question of which abelian groups we can do this in: we will characterize these groups in terms of the existence of certain functions on Γ called length functions, and in the finitely generated case in terms of the eigenvalues of F. We will also give a general notion of sparsity for F-automatic sets, called F-sparsity, and characterize F-sparsity in terms of length functions. Finally, we will examine how F-automaticity and F-sparsity interact with model theoretic tameness properties, namely stability and NIP.
Please contact Nancy Maloney (nfmalone@uwaterloo.ca) if you are interested in virtually attending Christopher's talk.