TY - GEN

T1 - A strong version of Cobham's theorem

AU - Hieronymi, Philipp

AU - Schulz, Christian

N1 - Funding Information:
The authors were partially supported by NSF grant DMS-1654725. We thank Chris Miller, Jeffrey Shallit and Erik Walsberg for helpful conversations around the topic of this paper.
Publisher Copyright:
© 2022 ACM.

PY - 2022/9/6

Y1 - 2022/9/6

N2 - Let k,g.,"≥ 2 be two multiplicatively independent integers. Cobham's famous theorem states that a set X† g.,• is both k-recognizable and g.,"-recognizable if and only if it is definable in Presburger arithmetic. Here we show the following strengthening: let X† g.,•m be k-recognizable, let Y† g.,•n be g.,"-recognizable such that both X and Y are not definable in Presburger arithmetic. Then the first-order logical theory of (g.,•,+,X,Y) is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of (g.,•,+,X) is decidable.

AB - Let k,g.,"≥ 2 be two multiplicatively independent integers. Cobham's famous theorem states that a set X† g.,• is both k-recognizable and g.,"-recognizable if and only if it is definable in Presburger arithmetic. Here we show the following strengthening: let X† g.,•m be k-recognizable, let Y† g.,•n be g.,"-recognizable such that both X and Y are not definable in Presburger arithmetic. Then the first-order logical theory of (g.,•,+,X,Y) is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of (g.,•,+,X) is decidable.

KW - Cobham's theorem

KW - Presburger arithmetic

KW - logical theories

KW - undecidability

UR - http://www.scopus.com/inward/record.url?scp=85132740116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132740116&partnerID=8YFLogxK

U2 - 10.1145/3519935.3519958

DO - 10.1145/3519935.3519958

M3 - Conference contribution

AN - SCOPUS:85132740116

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1172

EP - 1179

BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Leonardi, Stefano

A2 - Gupta, Anupam

PB - Association for Computing Machinery

T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022

Y2 - 20 June 2022 through 24 June 2022

ER -