  Graph polynomials which are definable in Monadic Second Order Logic (MSOL) on
the vocabulary of graphs are Fixed-Parameter Tractable (FPT) with respect to
clique-width. In contrast, graph polynomials which are definable in MSOL on the
vocabulary of hypergraphs are fixed-parameter tractable with respect to
tree-width, but not necessarily with respect to clique width. No algorithmic
meta-theorem is known for the computation of graph polynomials definable in
MSOL on the vocabulary of hypergraphs with respect to clique-width. We define
an infinite class of such graph polynomials extending the class of graph
polynomials definable in MSOL on the vocabulary of graphs and prove that they
are Fixed-Parameter Polynomial Time (FPPT) computable, i.e. that they can be
computed in time $O(n^{f(k)})$, where $n$ is the number of vertices and $k$ is
the clique-width.
