Typesetting A* in LaTeX using algorithm2e
Instead of writing \textsc and \text all the time, I prefer semantic markup, such as \func and \var. These simple name changes make the source code easier to read for me. Compare:

\var{p} = \func{prime}(\var{x})
\text{p} = \textsc{prime}(\text{x})


When reading the first line aloud, you will quickly notice any discrepancy between a name and its type.

It looks weird to me that the math mode is closed before the first \Nil and another math mode is opened again immediately after it. This could influence the spacing in subtle ways. It's probably better to write it like this:

$\pi = \{ (s \mapsto \text{\Nil})\}$


This wording feels more natural since there is really only a single math expression here.

The last \caption is not indented properly.