LOGIC AND p-RECOGNIZABLE SETS OF INTEGERS
LOGIC AND p-RECOGNIZABLE SETS OF INTEGERS
复制标题
DOI：
10.36045/bbms/1103408547
复制
发表时间：
1994
影响因子：
0.5
通讯作者：
Véronique Bruyàre;G. Hansel;C. Michaux;Roger Villemaire
中科院分区：
文献类型：
--
作者：
Véronique Bruyàre;G. Hansel;C. Michaux;Roger Villemaire
我们调查了以 p 进制展开形式编写的整数集的属性，这些整数集可以被自动机识别。我们重点关注 Cobham 定理，该定理描述了在不同基 p 中可识别的集合的特征，以及 Semenov 将其推广到 N m 的定理。我们详细介绍了穆奇尼克最近为科巴姆-谢苗诺夫定理给出的非凡证明，原始证明以俄语出版。
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 dierent bases p and on its generalization to N m due to Semenov. We detail the remarkable proof recently given by Muchnik for the theorem of Cobham-Semenov, the original proof being published in Russian.