Homomorphisms, i.e. M↑R↑C↑ transformations, are known to be very suitable as abstraction functions in heuristic search, 
cf.  the  articles  by Holte  et al. [59],  Helmert  et al. [48] and  Zilles  and  Holte [92].  One  reason  for  this  is  that  they  are 
admissible. The following result shows that also the opposite holds, admissibility implies that the abstraction function is a 
homomorphism, if all arcs in both graphs have unit cost. Without unit costs, this relationship breaks down. This is a most 
relevant observation in the context of using the path length in the abstract graph as the heuristic estimate for the path 
length or path cost in the ground graph.
Theorem 53. Let τ = (cid:3) f , R, w1, d2(cid:4) be an M↑A↓ transformation. Then:
1. If w1(s, t) < 2 or w1(s, t) = ∞ for all s, t ∈ S1, then f is a homomorphism.
2. Otherwise f need not be a homomorphism.
Proof. (1) Suppose  that  τ is  M↑A↓ and  w1(s, t) < 2 or  w1(s, t) = ∞ for  all  s, t ∈ S1.  Then  suppose  that  f
A-framework-for-analysing-state-abstraction-metho_2022_Artificial-Intelligen