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

MaRDI QIDQ6410014zbMATH OpenFDO

Authors Luke Schaeffer, Jeffrey Shallit

Publication date 7 September 2022

Abstract: 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<alphaleq7/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.

This page was built for publication: The First-Order Theory of Binary Overlap-Free Words is Decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6410014)