Logic and p-Recognizable Sets of Integers

V. Bruyère, G. Hansel, C. Michaux, R. Villemaire

IBP-Litp 1994/04: Rapport de Recherche Litp / Litp research reports
42 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Logic and p-Recognizable Sets of Integers

Résumé : Ce survey traite des propriétés d'ensembles d'entiers qui, écrits en base p, sont reconnaissables par automate fini. Nous nous intéressons plus particulièrement au théorème de Cobham qui caractérise les ensembles reconnaissables dans différentes bases p, ainsi qu'à sa généralisation à Nm proposée par Semenov. Nous détallions la preuve remarquable du théorème de Cobham-Semenov donnée récemment par Muchnik, la preuve originale étant publiée en Russe.

Abstract : We survey the properties of sets of integers recognizable by automata when they are written in p-ary expansions. We focus on Cobham's theorem which characterizes the sets recognizable in different bases p and on its generalization to Nm due to Semenov. We detail the remarkable proof recently given by Muchnik for Cobham-Semenov's theorem, the original proof being published in Russian.

Publications internes Litp 1994 / Litp research reports 1994