Decidability, complexity, and expressiveness of first-order logic over the subword ordering
Decidability, complexity, and expressiveness of first-order logic over the subword ordering
复制标题
子字排序上的一阶逻辑的可判定性、复杂性和表达性
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Georg Zetzsche
中科院分区：
文献类型：
--
作者：
Simon Halfon;P. Schnoebelen;Georg Zetzsche
我们考虑一阶逻辑的子字排序有限的话，每个字是一个常数。我们的第一个结果是，E1理论是不可判定的（已经超过两个字母）。我们调查的可判定性边界考虑片段，但一定数量的变量交替有界，这意味着变量必须始终量化的语言与有限数量的字母交替。我们证明，当最多两个变量不是交替有界的，该片段是可判定的，并成为不可判定的，当三个变量不是交替有界的。对于更高的量词交替深度，我们证明了对于一个没有交替界的变量，C12片段已经是不可判定的，并且当所有变量都是交替界时，整个一阶理论是可判定的。
We consider first-order logic over the subword ordering on finite words where each word is available as a constant. Our first result is that the Σ1 theory is undecidable (already over two letters). We investigate the decidability border by considering fragments where all but a certain number of variables are alternation bounded, meaning that the variable must always be quantified over languages with a bounded number of letter alternations. We prove that when at most two variables are not alternation bounded, the Σ1 fragment is decidable, and that it becomes undecidable when three variables are not alternation bounded. Regarding higher quantifier alternation depths, we prove that the Σ2 fragment is undecidable already for one variable without alternation bound and that when all variables are alternation bounded, the entire first-order theory is decidable.
关于故障通道机器的终止和不变性
影响因子：
1
作者：
Bouyer P
通讯作者：
Bouyer P