Publications > Preprint server > Preprint Number 1944
Preprint Number 1944
1944. Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, Jeffrey Shallit Decidability for Sturmian words E-mail: Submission date: 25 March 2021 Abstract: We show that the first-order theory of Sturmian words over Presburger arithmetic is decidable. Using a general adder recognizing addition in Ostrowski numeration systems by Baranwal, Schaeffer and Shallit, we prove that the first-order expansions of Presburger arithmetic by a single Sturmian word are uniformly ω-automatic, and then deduce the decidability of the theory of the class of such structures. Using an implementation of this decision algorithm called Pecan, we automatically reprove many classical theorems about Sturmian words in seconds, and are able to obtain new results about antisquares and antipalindromes in characteristic Sturmian words. Mathematics Subject Classification: Keywords and phrases: |
Last updated: April 9 2021 12:06 | Please send your corrections to: |