标题： 关于带有动态谓词的单二阶逻辑的展开 显示英文标题

标题： On Expansions of Monadic Second-Order Logic with Dynamical Predicates

摘要： 一阶谓词逻辑（MSO）理论在结构$\langle \mathbb{N} ; < \rangle$上的扩展自20世纪60年代Büchi以及Elgot和Rabin的开创性论文发表以来，一直是研究活跃且富有成果的领域。 在本文中，我们建立了$\langle \mathbb{N} ; <,P \rangle$的 MSO 理论的可判定性，其中$P$范围涵盖了一大类一元“动态”谓词，即某些整数线性递推序列所取的非负值集合。 我们的一个关键技术工具是（有效）prodisjunctivity 的新概念，我们预计它可能在其他领域也有独立的应用。 显示英文摘要

摘要： Expansions of the monadic second-order (MSO) theory of the structure $\langle \mathbb{N} ; < \rangle$ have been a fertile and active area of research ever since the publication of the seminal papers of B\"uchi and Elgot & Rabin on the subject in the 1960s. In the present paper, we establish decidability of the MSO theory of $\langle \mathbb{N} ; <,P \rangle$, where $P$ ranges over a large class of unary ''dynamical'' predicates, i.e., sets of non-negative values assumed by certain integer linear recurrence sequences. One of our key technical tools is the novel concept of (effective) prodisjunctivity, which we expect may also find independent applications further afield.