Explaining the decompositionality of MSO using applications to combinatorics

ABSTRACT. Abstract. Courcelle's celebrated theorem forms a strong theoretical basis for the development of formal methods. This extended abstract argues that a good intuition into the underlying ideas behind Courcelle's theorem can be achieved by considering the applications of these ideas to combinatorics. Technical notions regarding compuation are eliminated and replaced with simple notions of recurrence relations.