Jeffrey Shallit

activity

20172025

most citedDecidability and k-Regular Sequences

2 citations · 3 across the 11 of their papers we have counts for

collaborators

11 papers

cs.FL2025

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…

math.CO2025★ 1 cited

Runs in Paperfolding Sequences

Jeffrey Shallit

The paperfolding sequences form an uncountable class of infinite sequences over the alphabet ${- 1, 1}$ that describe the sequence of folds arising from iterated folding of a pi…

math.CO2025

Cloitre's Self-Generating Sequence

Jeffrey Shallit

In 2009 Benoit Cloitre introduced a certain self-generating sequence $(a_{n})_{n \geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \dots,$ with the property that the sum of th…

cs.FL2024

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…

math.CO2022

Some Tribonacci Conjectures

Jeffrey Shallit

In a recent talk of Robbert Fokkink, some conjectures related to the infinite Tribonacci word were stated by the speaker and the audience. In this note we show how to prove (or dis…

cs.FL2022

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 $α$ , $2 < α \leq 7/3$ ), is decidable. As a conseq…

math.CO2022

Record-Setters in the Stern Sequence

Ali Keramatipour, Jeffrey Shallit

Stern's diatomic series, denoted by $(a (n))_{n \geq 0}$ , is defined by the recurrence relations $a (2 n) = a (n)$ and $a (2 n + 1) = a (n) + a (n + 1)$ for $n \geq 1$ , and initial values…

cs.FL2022

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…

cs.FL2021

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…

cs.FL2020★ 2 cited

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…

math.CO2017

Continuants, run lengths, and Barry's modified Pascal triangle

Jeffrey Shallit, Lukas Spiegelhofer

We show that the $n$ 'th diagonal sum of Barry's modified Pascal triangle can be described as the continuant of the run lengths of the binary representation of $n$ . We also obtain a…