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
-
Extended abstract in
Proceedings of the Twenty-Fourth
International Colloquium on Automata, Languages, and Programming,
pages 805-815, 1997.