  We extend the notion of compositional associative rewriting as recently
studied in the rule algebra framework literature to the setting of rewriting
rules with conditions. Our methodology is category-theoretical in nature, where
the definition of rule composition operations encodes the non-deterministic
sequential concurrent application of rules in Double-Pushout (DPO) and
Sesqui-Pushout (SqPO) rewriting with application conditions based upon
$\mathcal{M}$-adhesive categories. We uncover an intricate interplay between
the category-theoretical concepts of conditions on rules and morphisms, the
compositionality and compatibility of certain shift and transport constructions
for conditions, and thirdly the property of associativity of the composition of
rules.
