On such "loopy" graphical models, exact inference is in general uncomputable when the random variables are string-valued.
dreyer and Eisner (2009) showed how to substitute a popular approximate joint inference method, loopy belief propagation (Murphy et al., 1999).