论文标题

无重叠词的一阶理论是可决定的

The First-Order Theory of Binary Overlap-Free Words is Decidable

论文作者

Schaeffer, L., Shallit, J.

论文摘要

我们表明,无重叠的单词的一阶逻辑理论(更一般而言,是理性$α$,$ 2 <α\ leq 7/3 $的$α$ free单词)是可决定的。结果,现在可以使用决策程序“自动”证明许多先前通过乏味的基于案例的证据获得的有关此类的结果。

We show that the first-order logical theory of the binary overlap-free words (and, more generally, the $α$-free words for rational $α$, $2 < α \leq 7/3$), is decidable. As a consequence, many results previously obtained about this class through tedious case- based proofs can now be proved "automatically", using a decision procedure.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源