While most plan recognition systems make use of a plan library that contains the set of available plan hypotheses, little effort has been devoted to the question of how to create such a library. This problem is particularly difficult to deal with when only little domain knowledge is available---a common situation when e.g. developing a help system for an already existing software system. This paper describes how operational decompositions of plans can be extracted from a set of sample action sequences, thus providing the basis for automating the acquisition of plan libraries. Efficient algorithms for the approximation of optimal decompositions and experimental results supporting their feasibility are presented.