Resource-bounded balanced genericity, stochasticity and weak randomness

• Verfasst von: Ambos-Spies, Klaus [VerfasserIn]
• Verfasst von: Mayordomo, Elvira [VerfasserIn]
• Verfasst von: Wang, Yongge [VerfasserIn]
• Verfasst von: Zheng, Xizhong [VerfasserIn]
• Titel: Resource-bounded balanced genericity, stochasticity and weak randomness
• Verf.angabe: Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng
• Jahr: 1996
• Umfang: 12 S.
• Fussnoten: Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005 ; Gesehen am 18.04.2023
• Titel Quelle: Enthalten in: STACS (13 : 1996 : Grenoble)Proceedings
• Ort Quelle: Berlin [u.a.] : Springer, 1996
• Jahr Quelle: 1996
• Band/Heft Quelle: (1996), Seite 63-74
• ISBN Quelle: 978-3-540-49723-3
• DOI: doi:10.1007/3-540-60922-9_6
• Datenträger: Online-Ressource
• Sprache: eng
• (Gesamttitel): Lecture Notes in Computer Science
• Sach-SW: Complexity Theory
• Sach-SW: Initial Segment
• Sach-SW: Prediction Function
• Sach-SW: Selection Function
• Sach-SW: Weak Notion
• K10plus-PPN: 1843050617

Abstract

We introduce balanced t(n)-genericity which is a refinement of the genericity concept of Ambos-Spies, Fleischhack and Huwig [2] and which in addition controls the frequency with which a condition is met. We show that this concept coincides with the resource-bounded version of Church's stochasticity [6]. By uniformly describing these concepts and weaker notions of stochasticity introduced by Wilber [19] and Ko [11] in terms of prediction functions, we clarify the relations among these resource-bounded stochasticity concepts. Moreover, we give descriptions of these concepts in the framework of Lutz's resource-bounded measure theory [13] based on martingales: We show that t(n)-stochasticity coincides with a weak notion of t(n)-randomness based on so-called simple martingales but that it is strictly weaker than t(n)-randomness in the sense of Lutz.