Decomposition-width: Extending the Clique-width to Hypergraphs

We define a width parameter for hypergraphs, which we call the decomposition-width. We provide an explicit family of hypergraphs of large decomposition-width and we prove that every MSO property can be checked in linear time for hypergraphs with bounded decomposition-width when their decomposition is given. Finally, the decomposition-width of a graph is proved to be bounded by twice its clique-width, which suggests that decomposition-width is a generalization of clique-width to relations of large or unbounded arity