{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:23Z","timestamp":1753894403154,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We show that the first-order theory of Sturmian words over Presburger\narithmetic is decidable. Using a general adder recognizing addition in\nOstrowski numeration systems by Baranwal, Schaeffer and Shallit, we prove that\nthe first-order expansions of Presburger arithmetic by a single Sturmian word\nare uniformly $\\omega$-automatic, and then deduce the decidability of the\ntheory of the class of such structures. Using an implementation of this\ndecision algorithm called Pecan, we automatically reprove classical theorems\nabout Sturmian words in seconds, and are able to obtain new results about\nantisquares and antipalindromes in characteristic Sturmian words.<\/jats:p>","DOI":"10.46298\/lmcs-20(3:12)2024","type":"journal-article","created":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T20:10:11Z","timestamp":1722888611000},"source":"Crossref","is-referenced-by-count":1,"title":["Decidability for Sturmian words"],"prefix":"10.46298","volume":"Volume 20, Issue 3","author":[{"given":"Philipp","family":"Hieronymi","sequence":"first","affiliation":[]},{"given":"Dun","family":"Ma","sequence":"additional","affiliation":[]},{"given":"Reed","family":"Oei","sequence":"additional","affiliation":[]},{"given":"Luke","family":"Schaeffer","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[]},{"given":"Jeffrey","family":"Shallit","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2024,8,5]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/14029\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/14029\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T20:10:12Z","timestamp":1722888612000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/9980"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,5]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(3:12)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2102.08207v4","asserted-by":"subject"},{"id-type":"arxiv","id":"2102.08207v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2102.08207","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2102.08207","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,8,5]]},"article-number":"9980"}}