Search

In 2016, Hamoon Mousavi published Walnut which is a program that implements automated theorem proving of propositions about automatic sequences. The main purpose of this thesis was to show the theoretical functi- onality of Walnut on the basis of the relation between automatic sequences and Presburger (resp. B¨uchi) arithmetic that is a decidable theory. Another goal was to describe adequately how the decision procedure of Walnut really works, and finally, to show the practical use of Walnut on several particular problems. One of these particular problems that are solved in the thesis is computation of the critical exponent of the Rudin-Shapiro sequence - this exercise was presented as an open problem in a book of 2003 (however, this exercise does not belong among open problems any more since Shallit proved in 2011 that the critical exponent is computable for all automatic sequences.) The last chapter itself can be also used as a brief manual for newcomers to Walnut that want to use this program for their own applications. 1

Automated theorem provers can be modified in order to use external sources of axioms. This was recently searched in combination with saturation based theorem prover SPASS-XDB. It sends queries to external sources and receives answers during its saturation loop. Lean theorem provers are based on semantic tableau calculus. That's why they need to use different approach. An idea that proving is separated from communication is beeing introduced by this work. Prover generetes so called schematic proof which is later checked if it can be filled with external data so the proof can be completed. This work demonstates this idea on modified version of LeanCoP.