Events
Fall 2016

# Logical Structures in Computation Seminar

Nov 30, 2016 4:00 pm – 5:00 pm

In 1981 C. Blatter and E. Specker gave an application of logic to combinatorics dealing with modular periodicity of combinatorial sequences. This arguably was the first statement of a "meta-theorem" in finite model theory. It states that combinatorial sequences (counting functions) definable in Monadic Second Order Logic are ultimately periodic modulo every integer $m$. In this talk we discuss further developments concerning this theorem and give new applications to graph polynomials. In particular we prove a conjecture by A. Mani and R. Stones from 2016.