2 citations · 2 across the 4 of their papers we have counts for
4 papers
An Improved Lower Bound for Stack Sorting
Luke Schaeffer
We consider the problem of sorting elements on a series of stacks, introduced by Tarjan and Knuth. We improve the asymptotic lower bound for the number of stacks necessary to sort…
Ostrowski Numeration and the Local Period of Sturmian Words
Luke Schaeffer
We show that the local period at position n in a characteristic Sturmian word can be given in terms of the Ostrowski representation for n + 1.
Avoiding Three Consecutive Blocks of the Same Size and Same Sum
Julien Cassaigne, James D. Currie, Luke Schaeffer +1
We show that there exists an infinite word over the alphabet {0, 1, 3, 4} containing no three consecutive blocks of the same size and the same sum. This answers an open problem of…
Decidability and Shortest Strings in Formal Languages
Levent Alpoge, Thomas Ang, Luke Schaeffer +1
Given a formal language L specified in various ways, we consider the problem of determining if L is nonempty. If L is indeed nonempty, we find upper and lower bounds on the length…