We study the algorithmic properties of first-order monomodal logics of frames $\langle \mathbb{N}, \leq \rangle$, $\langle \mathbb{N}, < \rangle$, $\langle \mathbb{Q}, \leq \rangle$, $\langle \mathbb{Q}, < \rangle$, $\langle \mathbb{R}, \leq \rangle$, $\langle \mathbb{R}, < \rangle$, as well as some related logics, in languages with restrictions on the number of individual variables as well as the number and arity of predicate letters. We show that the logics of frames based on $\mathbb{N}$ are $\Pi^1_1$-hard -- thus, not recursively enumerable -- in languages with two individual variables, one monadic predicate letter and one proposition letter. We also show that the logics of frames based on $\mathbb{Q}$ and $\mathbb{R}$ are $\Sigma^0_1$-hard in languages with the same restrictions. Similar results are obtained for a number of related logics.
翻译：我们用限制单个变量数量以及前提字母数量和有效性的语言, 研究第一级单式逻辑的算法特性 $\ langle \ mathbb{N},\leq\ rangle $, $\ langle \ rangle $, $\ langle \ \ mathbb}, <\ rangle$, $\ langle \ mathbb{R},\leq\ rangle$, $langle \ mathbb{R}, <\ ranglegle$, 以及一些相关的逻辑。 我们显示基于 $\ mathb{ N} 的框架逻辑值是 $\ 1_ 1\ 1 美元硬的, 因此, 不可重复 数字化 -- 语言有两个单独的变量, 一个monadiclegle claim 字母和一个首字母。 我们还显示基于 $1\\ mas basild 的逻辑值 和 $_ salbblock $.
相关内容
微信扫码咨询专知VIP会员