15 citations · 105 across the 64 of their papers we have counts for
10 papers · 1 filter
Optimal Regular Expressions for Permutations
Antonio Molina Lovett, Jeffrey Shallit
The permutation language consists of all words that are permutations of a fixed alphabet of size . Using divide-and-conquer, we construct a regular expression that s…
Cobham's Theorem and Automaticity
Lucas Mol, Narad Rampersad, Jeffrey Shallit +1
We make certain bounds in Krebs' proof of Cobham's theorem explicit and obtain corresponding upper bounds on the length of a common prefix of an aperiodic -automatic sequence an…
Circular critical exponents for Thue-Morse factors
Jeffrey Shallit, Ramin Zarifi
We prove various results about the largest exponent of a repetition in a factor of the Thue-Morse word, when that factor is considered as a circular word. Our results confirm and g…
The number of valid factorizations of Fibonacci prefixes
Pierre Bonardo, Anna E. Frid, Jeffrey Shallit
We establish several recurrence relations and an explicit formula for V(n), the number of factorizations of the length-n prefix of the Fibonacci word into a (not necessarily strict…
Additive Number Theory via Approximation by Regular Languages
Jason Bell, Thomas Finn Lidbetter, Jeffrey Shallit
We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural num…
Counting Subwords and Regular Languages
Charles J. Colbourn, Ryan E. Dougherty, Thomas F. Lidbetter +1
Let and be words. We consider the languages whose words are those for which the numbers of occurrences of and , as subwords of , are the same (resp., the numb…