A* shortest string decoding for non-idempotent semirings
arxiv.org