This is a (perhaps re-) implementation of an algorithm discovered by Arnborg, Courcelle, Proskurowski, and Seese. They discovered that, using rewrite rules, you can determine graph membership in linear time for any set of graphs with bounded treewidth that is describable in monadic second order logic. (Whew. That's a mouthful.) Unfortunately, the proof was non-constructive, which means tht you are on your own if you want to automagically generate an algorithm that checks whether or not a set of graphs has a particular property or not.

This program will allow you to tell whether or not a graph has a particular property, as long as the rewrite rules and the basis set of representatives are all written down.