While exact inference might be possible in our case, we used the simpler approach of adapting standard inference algorithms for linear-chain models.
to account for skip-edges, we used a technique inspired by (Sha and Pereira, 2003), in which multiple state dependencies, such as an order-2 Markov model, are encoded using auxiliary tags.