∞
s to t in  E. The exact deﬁnition of  w does not matter; it could be an arbitrary assignment, it could be based on a weight 
function on the labels such that  w(s, t) is the minimum weight of all labels on the arcs from  s to t etc. We extend the 
weight function to paths such that  w(s0, . . . , sk) = (cid:4)
i=1 w(si−1, si). Although it is common that the arc weights are given 
by  the  labels  (i.e.  the  actions),  it  is  usually  only  the  weights  that  are  considered  when  computing  heuristics,  so  in  that 
sense, the actual labels are irrelevant. Following common practice in this context, we only consider cost functions that are 
implicitly deﬁned by the weight function w such that c(s, t) is the minimum of w(σ ) over all paths σ from s to t, i.e. c(s, t)
is the cost of the cheapest path from s to t. Note that c(s, t) = ∞ if and only if there is no path from s to t. We also deﬁne
A-framework-for-analysing-state-abstraction-metho_2022_Artificial-Intelligen