|
A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals
Bruno Courcelle (Laboratoire d'Informatique, Université Bordeaux-I, CNRS 351, Cours de la Libération, France)
Rodney G. Downey (Department of Mathematics, Victoria University, New Zealand)
Michael R. Fellows (Department of Computer Science, University of Victoria, Canada)
Abstract: The major results of Robertson and Seymour on graph well-quasi-ordering establish nonconstructively that many natural graph properties that constitute ideals in the minor or immersion orders are characterized by a finite set of forbidden sub- structures termed the obstructions for the property. This raises the question of what general kinds of information about an ideal are sufficient, or insufficient, to allow the obstruction set for the ideal to be effectively computed. It has been previously shown that it is not possible to compute the obstruction set for an ideal from a description of a Turing machine that recognizes the ideal. This result is significantly strengthened in the case of the minor ordering. It is shown that the obstruction set for an ideal in the minor order cannot be computed from a description of the ideal in monadic second-order logic.
1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.
Keywords: decidability, monadic second order logic, well-quasi-ordering
Categories: F.4, G.2
|
