Some cryptographic papers use $H^n(x)$ to mean $H(H^{n-1}(x))$ where $H^0(x) = x$ and $H$ is a cryptographic hash. So $H^3(x)$ would be $H(H(H(x)))$.
Is this definition formally correct? It seems to me that cryptographic hash functions are not associative. Does at least power-associativity hold for hash functions?
If it formally shouldn't be written like this, what would be a mathematically correct & short way of describing this kind of functionality?
For a Q/A about what $H^n(x)$ means please see the Q/A on crypto here.
We have an associative operation here – it is the function composition $\circ$.
For any functions $f : X \to Y$ and $g : Y \to Z$ we have $g \circ f : X \to Z$, defined by $(g \circ f)(x) := g(f(x))$ for all $x \in X$. I heard some authors defined it the other way around, $(f \circ g)(x) := g(f(x))$. I think my version is more common.) This operation is obviously associative, where defined: $$((f \circ g) \circ h)(u) = (f \circ g)(h(u)) = f(g(h(u))) = f((g \circ h)(u)) = (f \circ (g \circ h))(u),$$ thus $(f \circ g) \circ h = f \circ (g \circ h)$.
For functions from one set to itself (i.e. $f : X \to X$) we can compose $f$ with itself, and have then $f \circ f$, $f \circ f \circ f$ and so on, and it is natural to name them $f^2$, $f^3$, etc. This naturally extends to $f^1 = f$ and $f^0 = \operatorname{id}_X$, with $\operatorname{id}_X : X \to X$ being the identity function of $X$ ($\operatorname{id}_X(x) = x$ for all $x \in X$).
When $f$ is bijective, we also naturally have $f^{-1}$, and generally $f^{-n}$, and all the usual properties of powers work: $f^n \circ f^{m} = f^{n+m}$, for example. The power laws actually don't need inverses for non-negative exponents.
The set of all bijective functions from a Set to itself forms a (non-commutative) group with this operations. These groups, as well as many of their subgroups (groups of bijections, which also retain some structural properties = isomorphism groups) are important objects of study.
But your hash functions are usually not bijective, thus they have no inverses, so we get no group. Still the set of functions $h : \{0,1\}^* \to \{0,1\}^*$ is a monoid under composition (associative with a neutral element – the identity function).
Looking just at "hash functions" with a given output size $n$, the set of functions $h : \{0,1\}^* \to \{0,1\}^n \subset \{0,1\}^*$ (which can be seen as a subset of the previous set) still works with the composition, though here there is no working neutral element – so we just have a semigroup.
For confusion
Sometimes we use the notation $f^n$ for a different function, namely the function defined by $(f^n)(x) := (f(x))^n$. This obviously only makes sense for $f : X \to Y$, when there is an obvious exponentiation operation in $Y$.
This exponentiation is then related to the "point-wise multiplication" operation $f · g : X \to Y$, defined by $(f ·g)(x) = f(x) · g(x)$, which is associative whenever multiplication in $Y$ is associative, and has the constant $\operatorname{const}_{1_Y}$-function as an identity (assuming $1_Y$ is a neutral element in $(Y, ·)$.
This often occurs when talking about real functions, like $\sin^2 + \cos^2 = 1$ meaning $(\sin(\alpha))^2 + (\cos(\alpha))^2 = 1$ (Pythagoras' theorem applied to the unit circle), not $\sin(\sin(\alpha)) + \cos(\cos(\alpha)) = 1$.
It is usually clear from context which meaning of $\square^n$ is meant – in the case of hash functions, we have no obvious multiplication of bitstrings, so the second meaning can't be the right one.