2014/12/20 by Elisabeth Paulson, Paulson, Elisabeth, Christopher Griffin +1
Computer Science · Mathematics · #90C27 #90C60 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Optimization and Control (math.OC) #cs.DS #cs.FL #math.OC #msc:90C27 #msc:90C60
paper · pdf · doi:10.48550/arxiv.1501.01300
Updated from original paper with improved proofs of result
arxiv created 2017/02/25 · arxiv updated 2017/02/28
In this paper, we study the problem of determining a minimum state probabilistic finite state machine capable of generating statistically identical symbol sequences to samples provided. This problem is qualitatively similar to the classical Hidden Markov Model problem and has been studied from a practical point of view in several works beginning with the work presented in: Shalizi, C.R., Shalizi, K.L., Crutchfield, J.P. (2002) An algorithm for pattern discovery in time series. Technical Report 02-10-060, Santa Fe Institute. arxiv.org/abs/cs.LG/0210025. We show that the underlying problem is NP-hard and thus all existing polynomial time algorithms must be approximations on finite data sets. Using our NP-hardness proof, we show how to construct a provably correct algorithm for constructing a minimum state probabilistic finite state machine given data and empirically study its running time.