2016/10/17 by Tong Zhang, Zhang, Tong
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.1610.08910
openalex publication_date 2016/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.