Geodesic
The first-order theory of binary overlap-free words is decidable
Canadian journal of mathematics, Tome 76 (2024) no. 4, pp. 1144-1162

Voir la notice de l'article provenant de la source Cambridge

DOI

We show that the first-order logical theory of the binary overlap-free words (and, more generally, the $\alpha $-free words for rational $\alpha $, $2 < \alpha \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, and new claims can be proved or disproved simply by restating them as logical formulas.
DOI : 10.4153/S0008414X23000342
Mots-clés : first-order logic, decidable theory, overlap-free word, finite automata, decision procedure, Büchi arithmetic 
Schaeffer, Luke; Shallit, Jeffrey. The first-order theory of binary overlap-free words is decidable. Canadian journal of mathematics, Tome 76 (2024) no. 4, pp. 1144-1162. doi: 10.4153/S0008414X23000342
@article{10_4153_S0008414X23000342,
     author = {Schaeffer, Luke and Shallit, Jeffrey},
     title = {The first-order theory of binary overlap-free words is decidable},
     journal = {Canadian journal of mathematics},
     pages = {1144--1162},
     year = {2024},
     volume = {76},
     number = {4},
     doi = {10.4153/S0008414X23000342},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008414X23000342/}
}
TY  - JOUR
AU  - Schaeffer, Luke
AU  - Shallit, Jeffrey
TI  - The first-order theory of binary overlap-free words is decidable
JO  - Canadian journal of mathematics
PY  - 2024
SP  - 1144
EP  - 1162
VL  - 76
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008414X23000342/
DO  - 10.4153/S0008414X23000342
ID  - 10_4153_S0008414X23000342
ER  - 
%0 Journal Article
%A Schaeffer, Luke
%A Shallit, Jeffrey
%T The first-order theory of binary overlap-free words is decidable
%J Canadian journal of mathematics
%D 2024
%P 1144-1162
%V 76
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008414X23000342/
%R 10.4153/S0008414X23000342
%F 10_4153_S0008414X23000342

Cité par Sources :