Conference abstracts

Session B3 - Symbolic Analysis

July 14, 14:30 ~ 14:55

Finite automata, automatic sets, and difference equations

Michael Singer

North Carolina State University, USA   -

A finite automaton is one of the simplest models of computation. Initially introduced by McCulloch and Pitts to model neural networks, they have been used to aid in software design as well as to characterize certain formal languages and number-theoretic properties of integers. A set of integers is said to be m-automatic if there is a finite automaton that decides if an integer is in this set given its base-m representation. For example powers of 2 are 2-automatic but not 3-automatic. This latter result follows from a theorem of Cobham describing which sets of integers are m- and n-automatic for sufficiently distinct m and n. In recent work with Reinhard Schaefke, we gave a new proof of this result based on analytic results concerning normal forms of systems of difference equations. In this talk, I will describe this circle of ideas.

View abstract PDF

FoCM 2017, based on a nodethirtythree design.