2 citations · 3 across the 11 of their papers we have counts for
6 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…
Strongly k-recursive sequences
Daniel Krenn, Jeffrey Shallit
Drawing inspiration from a recent paper of Heuberger, Krenn, and Lipnik, we define the class of strongly k-recursive sequences. We show that every k-automatic sequence is strongly…
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…
Decidability and k-Regular Sequences
Daniel Krenn, Jeffrey Shallit
In this paper we consider a number of natural decision problems involving k-regular sequences. Specifically, they arise from - lower and upper bounds on growth rate; in particular…