8 citations · 20 across the 21 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.CC2010★ 1 cited
Normalized Information Distance is Not Semicomputable
Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitanyi
Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of…
math.LO2010★ 2 cited
Intuitionistic Logic and Muchnik Degrees
Andrea Sorbi, Sebastiaan A. Terwijn
We prove that there is a factor of the Muchnik lattice that captures intuitionistic propositional logic. This complements a now classic result of Skvortsova for the Medvedev lattic…