15 citations · 86 across the 34 of their papers we have counts for
5 papers · 2 filters
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…
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…
Finite Orbits of Language Operations
E. Charlier, M. Domaratzki, T. Harju +1
We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. T…
Fife's Theorem Revisited
Jeffrey Shallit
We give another proof of a theorem of Fife - understood broadly as providing a finite automaton that gives a complete description of all infinite binary overlap-free words. Our pro…