  We develop a framework for linear-programming (LP) decoding of non-binary
linear codes over rings. We prove that the resulting LP decoder has the
`maximum likelihood certificate' property, and we show that the decoder output
is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the
linear program and pseudocodewords of graph covers is proved. LP decoding
performance is illustrated for the (11,6,5) ternary Golay code with ternary PSK
modulation over AWGN, and in this case it is shown that the LP decoder
performance is comparable to codeword-error-rate-optimum hard-decision based
decoding.
