SFI Working Paper Abstract
1990
| Title: | A Relation between Complexity and Entropy for Markov Chains and Regular Languages |
| Author(s): | Wentian Li |
| Files: | [No electronic files available.] |
| Paper #: | 90-025 |
| Abstract: | By using the mutual information between two semi-infinite blocks as a measure of complexity, the relation between the complexity and the metric entropy is determined analytically for one-step two-state Markov chains as well as several regular languages. Similar procedures should be applicable to other sequences with short range correlations. Also discussed is the convergence rate of the block entropy towards the limiting straight line; if the convergence rate is too slow, the complexity as numerically calculated from a finite size can be quite different from that derived at the infinite size limit. |