[amelius]

This makes me wonder. Is Mathematica also applying a bag of tricks (I suppose in a breadth first search), or does it have a more structural approach?

[qubex]

As I recall, Mathematica embodies a (perhaps incomplete) implementation of the Risch algorithm.