Concurrent recursive programs (even over a finite data domain) are Turing-powerful. One way to circumvent this is to identify decidable under-approximations.
The behaviours of concurrent recursive programs can be described as graphs where the nodes represent events and the edges denote communication or sequencing. An underapproximation identifies a collection graphs representing the set of permitted behaviours.
The theory of graph decompositions provides measures on the structure of graphs (eg. tree-width, clique-width, path-width, split-width and so on). We examine the connection between decidability of under-approximations and measures on the behaviours they admit.