Transduction of Automatic Sequences and Applications

Abstract

We consider the implementation of the transduction of automatic sequences, and their generalizations, in the Walnut software for solving decision problems in combinatorics on words. We provide a number of applications, including (a) representations of n! as a sum of three squares (b) overlap-free Dyck words and (c) sums of Fibonacci representations. We also prove results about iterated running sums of the Thue-Morse sequence.