  For hidden Markov models one of the most popular estimates of the hidden
chain is the Viterbi path -- the path maximising the posterior probability. We
consider a more general setting, called the pairwise Markov model (PMM), where
the joint process consisting of finite-state hidden process and observation
process is assumed to be a Markov chain. It has been recently proven that under
some conditions the Viterbi path of the PMM can almost surely be extended to
infinity, thereby defining the infinite Viterbi decoding of the observation
sequence, called the Viterbi process. This was done by constructing a block of
observations, called a barrier, which ensures that the Viterbi path goes trough
a given state whenever this block occurs in the observation sequence. In this
paper we prove that the joint process consisting of Viterbi process and PMM is
regenerative. The proof involves a delicate construction of regeneration times
which coincide with the occurrences of barriers. As one possible application of
our theory, some results on the asymptotics of the Viterbi training algorithm
are derived.
