1 citations · 1 across the 5 of their papers we have counts for
5 papers
A Characterization of Morphic Words with Polynomial Growth
Tim Smith
A morphic word is obtained by iterating a morphism to generate an infinite word, and then applying a coding. We characterize morphic words with polynomial growth in terms of a new…
Sums of Palindromes: an Approach via Automata
Aayush Rajasekaran, Jeffrey Shallit, Tim Smith
Recently, Cilleruelo, Luca, & Baxter proved, for all bases b >= 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome. Ho…
Undecidability and Finite Automata
Jörg Endrullis, Jeffrey Shallit, Tim Smith
Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove thr…
Prediction of Infinite Words with Automata
Tim Smith
In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters…
On Infinite Words Determined by Indexed Languages
Tim Smith
We characterize the infinite words determined by indexed languages. An infinite language determines an infinite word if every string in is a prefix of . If is re…