Block Decomposition Method for Strings


Block Decomposition Method for Unweighted Adjacency Matrices

Algorithmic Complexity for Short Strings

Use space to separate strings.

The length of each string must be shorter than 13 characters.


Result of Evaluation




$$\textit{BDM} = \sum_{i=1}^{n} \textit{K}(\textit{block}_{i}) +\textit{log}_{2}(|\textit{block}_{i}|)$$


Strings that don't appear in the \(D(\#\textit{of states}, \#\textit{ of symbols})\) distribution have their \(\textit{K}\) value estimated as

$$ \textit{Max}(K(\#\textit{ of states}, \#\textit{ of symbols})) + 1 $$


Adjacency Matrix


Result of Evaluation


$$BDM = \sum_{i=1}^{n} K(block_{i})+log_{2}(|block_{i}|)$$


Result of Evaluation



$$K(\#\textit{ of states}, \#\textit{ of symbols}) = -log_{2}(D(\#\textit{of states}, \textit{# of symbols})$$


\(\textit{}~\)\(K(\#\textit{ of states}, \#\textit{ of symbols})\) indicates the estimated Kolmogorov complexity of the string by the Coding Theorem Method.


\(D(\#\textit{of states}, \#\textit{ of symbols})\) indicates the estimated algorithmic probability, which is the output frequency of the string by Turing machines with the same alphabet.


Strings that don't appear in the \(D(\#\textit{of states}, \#\textit{ of symbols})\) distribution have their \(\textit{K}\) value estimated as

$$ \textit{Max}(K(\#\textit{ of states}, \#\textit{ of symbols})) + 1 $$


More information on the other complexity functions is available in the documentation of the ACSS package @ CRAN.