MDPs, NMRDPs, Equivalence

We start with some notation and definitions. Given a finite set $S$ of states, we write $S^*$ for the set of finite sequences of states over $S$, and $S^\omega$ for the set of possibly infinite state sequences. Where `$\Gamma$' stands for a possibly infinite state sequence in $S^\omega$ and $i$ is a natural number, by `$\Gamma_i$' we mean the state of index $i$ in $\Gamma$, by `$\Gamma(i)$' we mean the prefix $\langle \Gamma_0, \ldots, \Gamma_i \rangle \in S^{*}$ of $\Gamma$. $\Gamma;\Gamma'$ denotes the concatenation of $\Gamma\in S^*$ and $\Gamma' \in S^\omega$.


Sylvie Thiebaux 2006-01-20