Skip to main content

What can the graph-structure of an automaton tell us about the support of its corresponding sequence?

Posted in
Speaker: 
Mieke Wessel
Zugehörigkeit: 
Göttingen
Datum: 
Fre, 20/06/2025 - 11:15 - 11:45
Location: 
MPIM Seminar Room

By a Theorem of Cobham, it is known that the support of an automatic sequence up to N grows either polylogarithmically in N or at least as a fractional power of N. We will illustrate a new proof of this that uses graph-theoretic tools. To do this we introduce the notion of a cycle arborescence and its height and we will explain where this height shows up in the asymptotic formula for both cases.

© MPI f. Mathematik, Bonn Impressum & Datenschutz
-A A +A