Hochschild homology of structured algebras

We give a general method for constructing explicit and natural operations on the Hochschild complex of algebras over any PROP with $A_\infty$--multiplication---we think of such algebras as $A_\infty$--algebras "with extra structure". As applications, we obtain an integral version of the Costello-Kontsevich-Soibelman moduli space action on the Hochschild complex of open TCFTs, the Tradler-Zeinalian action of Sullivan diagrams on the Hochschild complex of strict Frobenius algebras, and give applications to string topology in characteristic zero. Our main tool is a generalization of the Hochschild complex.