Relational approaches to represent and solve MDPs exploit structure that is inherent to modelled domains in order to avoid or at least reduce the impact of the curse of dimensionality that propositional representations suffer from. By explicitly reasoning about relational structure, policies that lead to specific goals can be derived on a very general, abstract level; thus, these policies are valid for numerous domain instantiations, regardless of the particular objects participating in it. This paper describes the encoding of relational MDPs as rewrite theories, allowing for highly domain-specific domain encoding and abstraction. Narrowing is employed to solve these relational MDPs symbolically. Resulting symbolic value functions are simplified by Ax-matching abstract state terms. It is shown that relational state representations significantly reduce the size of state space and value function when compared to propositional representations.