Monadic second order logic, tree automata and forbidden minors

N.Robertson and P.D.Seymour proved that each minor closed class K of graphs is characterized by finitely many minimal forbidden minors. If these minors are given then they can be used to find an efficient membership test for such classes (see [Rob Sey 86b]). From these minors one can get a monadic second order description of the class K. Main result of the article is that from a monadic second order description of the class K. Main result of the article is that from a monadic second order description of K the minimal forbidden minors can be constructed, when K contains only graphs of universally bounded tree width. The result is applied to the class of partial 2-pathes.