Browsing by Author "REIMANN, Jan"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Hierarchies of Randomness Tests
    (2006-02-10T06:54:28Z) REIMANN, Jan; STEPHAN, Frank
    It is well known that Martin-Loef randomness can be characterized by a number of equivalent test concepts, based either on effective nullsets (Martin-Loef and Solovay tests) or on prefix-free Kolmogorov complexity (lower and upper entropy). These equivalences are not preserved as regards the partial randomness notions induced by effective Hausdorff measures or partial incompressibility. Tadaki as well as Calude, Staiger and Terwijn studied several concepts of partial randomness, but for some of them the exact relations remained unclear. In this paper we will show that they form a proper hierarchy of randomness notions, namely for any rho where rho(x) is 2 to the power of -|x|s and s is a rational number satisfying 0