Logic Seminar

Tuesday, March 14, 2023 2:30 pm - 2:30 pm EDT (GMT -04:00)

Alexi Block Gorman, McMaster University

"Toward a characterization of V_k-definability"

Buchi automata are the natural extension of finite automata to a model of computation that accepts infinite-length inputs. We say a subset X of the reals is k-regular if there is a Buchi automaton that accepts (one of) the base-k representations of every element of X, and rejects the base-k representations of each element in its complement. Such sets include the classical two-thirds Cantor set. In general, call a subset of the reals a Cantor set if it is nonempty, compact, has no isolated points, and no interior.  Let V_k be a ternary predicate on Euclidean 3-space such that V_k(x,u,d) holds if and only if u is an integer power of k, and d is the coefficient of the term u in some base-k expansion of x. For a fixed k, all of the k-regular subsets of Euclidean space are definable in the expansion of the reals as an ordered additive group by the predicate V_k. In this talk, we will discuss current and ongoing progress toward a characterization of when we can define the V_k relation, and hence all k-regular subsets of Euclidean space, from an arbitrary k-regular Cantor set.

MC 5479