**
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