Friday, August 13, 2021 — 9:00 AM EDT

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.

Event tags 

S M T W T F S
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2021 (102)
    1. October (15)
    2. September (5)
    3. August (15)
    4. July (17)
    5. June (15)
    6. May (1)
    7. April (4)
    8. March (11)
    9. February (9)
    10. January (10)
  2. 2020 (103)
    1. December (10)
    2. November (12)
    3. October (4)
    4. September (3)
    5. August (1)
    6. July (5)
    7. June (1)
    8. May (3)
    9. March (16)
    10. February (26)
    11. January (22)
  3. 2019 (199)
  4. 2018 (212)
  5. 2017 (281)
  6. 2016 (335)
  7. 2015 (211)
  8. 2014 (235)
  9. 2013 (251)
  10. 2012 (135)