Tree-width and clique-width are two important graph parameters for obtaining Fixed-parameter tractable (FPT) graph algorithms. In particular for problems expressible in monadic second-order (MSO) logic. FPT algorithms can be based on finite automata.

The huge size problem is solved by means of fly-automata (FA) that compute their transitions (they cannot be tabulated). FA have been implemented and tested. Fly-Automata run on algebraic terms denoting the input graphs, and reflecting appropriate decompositions (in particular, tree-decompositions).

The algebraic operations upon which clique-width is based make easy the construction of FA from logical formulas and can also represent tree-decompositions, but there is in bad cases an exponential jump in widths. However, we have linear bounds on clique-width in terms of tree-width for sparse graphs: planar graphs, graph of bounded degree, incidence graphs and 1-planar graphs. These results hold for directed graphs. Incidence graphs allow to check MSO formulas with edge set quantifications for graphs of bounded tree-width.