1 citations · 2 across the 4 of their papers we have counts for
4 papers
Sophistication vs Logical Depth
Luís Antunes, Bruno Bauwens, Andre Souto +1
Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable fun…
On the logical depth function
L. Antunes, A. Souto, A. Teixeira +1
For a finite binary string its logical depth for significance is the shortest running time of a program for of length . There is another definition of logic…
Measuring communication complexity using instance complexity with oracles
Armando Matos, Andreia Teixeira, Andre Souto
We establish a connection between non-deterministic communication complexity and instance complexity, a measure of information based on algorithmic entropy. Let , $\o…
Entropy Measures vs. Algorithmic Information
Andreia Teixeira, Andre Souto, Armando Matos +1
Algorithmic entropy and Shannon entropy are two conceptually different information measures, as the former is based on size of programs and the later in probability distributions.…