15 citations · 86 across the 34 of their papers we have counts for
8 papers · 1 filter
Shuffling and Unshuffling
D. Henshall, N. Rampersad, J. Shallit
We consider various shuffling and unshuffling operations on languages and words, and examine their closure properties. Although the main goal is to provide some good and novel exer…
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…
A Pattern Sequence Approach to Stern's Sequence
Michael Coons, Jeffrey Shallit
Let w be a binary string and let a_w (n) be the number of occurrences of the word w in the binary expansion of n. As usual we let s(n) denote the Stern sequence; that is, s(0)=0, s…
Remarks on separating words
Erik D. Demaine, Sarah Eisenstat, Jeffrey Shallit +1
The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length <= n (by accepting one and rejecting the other). In this paper…
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…
A variant of Hofstadter's sequence and finite automata
J. -P. Allouche, J. Shallit
Following up on a paper of Balamohan, Kuznetsov, and Tanny, we analyze a variant of Hofstadter's Q-sequence and show it is 2-automatic. An automaton computing the sequence is expli…