On the Relationship between Complexity and Entropy for Markov Chains and Regular Languages.
Wentian Li · 1991
Abstract. Using the past-future mutual information as a measure of complexity, the relation between the complexity and the Shannon entropy is determined analytically for sequences generated by Markov chains and regular languages. It is emphasized that, given an entropy value, there are many possible complexity values, and vice versa; that is, the relationship between complexity and entropy is not one-toone, but rather many-to-one or one-to-many. It is also emphasized that there are structures in the complexity-versus-entropy plots, and these structures depend on the details of a Markov chain or a regular language grammar. 1.