Recognizability equals definability for partial k-paths

Valentine Kabanets

Abstract

We prove that every recognizable family of partial k-paths is definable in a counting monadic second-order logic. We also show the obstruction set of the class of partial k-paths computable for every k.

Versions