  The Stochastic Context Tree (SCOT) is a useful tool for studying infinite
random sequences generated by an m-Markov Chain (m-MC). It captures the
phenomenon that the probability distribution of the next state sometimes
depends on less than m of the preceding states. This allows compressing the
information needed to describe an m-MC. The SCOT construction has been earlier
used under various names: VLMC, VOMC, PST, CTW. In this paper we study the
possibility of reducing the m-MC to a 1-MC on the leaves of the SCOT. Such
context trees are called perfect-memory. We give various combinatorial
characterizations of perfect-memory context trees and an efficient algorithm to
find the minimal perfect-memory extension of a SCOT.

Logic in Computer Science;Data Structures and Algorithms