Despite significant advances in the development of model checking, it remains a difficult task in the hands of experts to make it scale to the size of industrial systems. A key step in achieving scalability is to “divide-and-conquer”, that is, to break up the veri.cation of a system into smaller tasks that involve the verification of its components. Assume-guarantee reasoning [9, 11] is a widespread “divide-and-conquer” approach that uses assumptions when checking individual components of a system. Assumptions essentially encode expectations that each component has from the rest the system in order to operate correctly. Coming up with the right assumptions is typically a non-trivial manual process, which limits the applicability of this type of reasoning in practice.