I'll add Minimum Description Length to the mix. Under certain definitions and conditions, it equals the Bayesian Information Criterion plus an extra term, which I consider a very interesting result in this "two faces of the same coin" perspective.

This is exactly why I think they are one and the same. It's relatively trivial to just plop a (lossy) machine learned markov chain instead of one learned (perfectly) from the data into PPM. With zero changes to the rest of the algorithm.