4 papers · 1 filter
Self-Verifying Predicates in Büchi Arithmetic
Mazen Khodier, Luke Schaeffer, Jeffrey Shallit
We discuss a technique, based on Angluin's algorithm, for automatically generating finite automata for various kinds of useful first-order logic formulas in Büchi arithmetic. Const…
The First-Order Theory of Binary Overlap-Free Words is Decidable
L. Schaeffer, J. Shallit
We show that the first-order logical theory of the binary overlap-free words (and, more generally, the -free words for rational , ), is decidable. As a conseq…
Note on a Fibonacci Parity Sequence
Jeffrey Shallit
Let ftm = 0111010010001... be the analogue of the Thue-Morse sequence in Fibonacci representation. In this note we show how, using the Walnut theorem-prover, to obtain a measure of…
Hilbert's spacefilling curve described by automatic, regular, and synchronized sequences
Jeffrey Shallit
We describe Hilbert's spacefilling curve in several different ways: as an automatic sequence of directions,as a regular and synchronized sequence of coordinates of lattice points e…