Appears in collection : Combinatorics, Automata, and Number Theory (CANT) school-conference / Ecole-conférence de Combinatoire, d'Automates et de Théorie des Nombres (CANT)
Büchi famously established the decidability of the monadic secondorder (MSO) theory of the structure (N,<) in his 1962 seminal paper, in so doing bringing to light a profound connection between logic and automata theory. His work was quickly followed by further decidability results concerning expansions of (N,<) by various arithmetic predicates (such as powers of 2, powers of 3, perfect squares, factorial numbers, etc.), but only one at a time. These results, due to Elgot and Rabin, relied on the novel ""contraction method"", a form of effective profinite ultimate periodicity. Last year, exploiting and combining techniques from dynamical systems and number theory, Berthé et al. investigated the decidability (N,<) expanded with several power predicates simultaneously. This mini-course will review some of the key relevant classical techniques and results from the 1960s to today.
By Joël Ouaknine
By Joël Ouaknine
