Submission date: 7 September 2022

Abstract:

We show that the first-order logical theory of the binary overlap-free words (and, more generally, the α-free words for rational α, 2 < α ≤ 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.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2209.03266: pdf, ps.