Here is an F# version - just for kicks
See F# source here: http://fsviterbi.codeplex.com/SourceControl/changeset/view/64363#1117175
Actual code (excluding comments) is slighly shorter due to F#'s better type inference and buit-in tuple support.
Path copying is avoided due to 'structural sharing' of F# collections (list in this case)
The double loop calculation is parallelized using TPL wapper "PSeq" but can be easily serialized. This could be useful for very large state sets on multi-core machines.