AUTOMATIC THEOREM-PROVING IN COMBINATORICS ON WORDS

作者：Goc Daniel^*; Henshall Dane; Shallit Jeffrey

来源：International Journal of Foundations of Computer Science, 2013, 24(6): 781-798.

DOI：10.1142/S0129054113400182

• Automatic theorem-proving
• combinatorics on words
• automatic sequence
• finite automata
• decidability
• borders
• linear recurrence
• periods
• enumeration

We describe a technique for mechanically proving certain kinds of theorems in combinatorics on words, using finite automata and a software package for manipulating them. We illustrate our technique by applying it to (a) solve an open problem of Currie and Saari on the lengths of unbordered factors in the Thue-Morse sequence; (b) verify an old result of Prodinger and Urbanek on the regular paperfolding sequence; (c) find an explicit expression for the recurrence function for the Rudin-Shapiro sequence; and (d) improve the avoidance bound in Leech%26apos;s squarefree sequence. We also introduce a new measure of infinite words called condensation and compute it for some famous sequences. We follow up on the study of Currie and Saari of least periods of infinite words. We. show I hat the characteristic sequence of least periods of a k-automatic sequence is (effectively) k-automatic. We compute the least periods for several famous sequences. Many of our results were obtained by machine computations.

• 出版日期2013-9