一句话：研究带算术谓词的自然数序结构的一元二阶理论可判定性，并给出若干无条件与条件性判定结果。
本文研究自然数结构 (N;<,P1,…,Pk) 的一元二阶（MSO）理论的可判定性，其中 P_i 为不同的一元谓词。重点考察线性递推序列研究中出现的“算术”谓词，如固定底数幂 Pow_k={k^n:n∈N}、k 次幂 N^k、Fibonacci 序列项集 Fib={0,1,2,3,5,8,13,…}，以及具有单个非重复主特征根的其它线性递推序列。作者获得了若干新的无条件与条件性可判定性结果；所提供的摘要未展开具体样本。
We investigate the decidability of the monadic second-order (MSO) theory of the structure (N; <, P1,…,Pk), for various unary predicates P1,…,Pk ⊆ N. We focus in particular on 'arithmetic' predicates arising in the study of linear recurrence sequences, such as fixed-base powers Powk = {kn : n ∈ N}, k-th powers Nk = {nk : n ∈ N}, and the set of terms of the Fibonacci sequence Fib = {0, 1, 2, 3, 5, 8, 13,…} (and similarly for other linear recurrence sequences having a single, non-repeated, dominant characteristic root). We obtain several new unconditional and conditional decidability results, a select sample of which are the following:
@inproceedings{paperbot8079,
title = {On the Decidability of Monadic Second-Order Logic with Arithmetic Predicates},
author = {Valérie Berthé and Toghrul Karimov and Joris Nieuwveld and Joël Ouaknine and Mihir Vahanwala and James Worrell},
booktitle = {LICS},
year = {2024},
doi = {10.1145/3661814.3662119}
}