Resource-bounded balanced genericity, stochasticity and weak randomness
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 stochasti...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Kapitel/Artikel Konferenzschrift |
| Sprache: | Englisch |
| Veröffentlicht: |
1996
|
| In: |
Proceedings
Year: 1996, Pages: 63-74 |
| Online-Zugang: |
|
| Verfasserangaben: | Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1843050617 | ||
| 003 | DE-627 | ||
| 005 | 20250116141800.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 230418s1996 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1007/3-540-60922-9_6 |2 doi | |
| 035 | |a (DE-627)1843050617 | ||
| 035 | |a (DE-599)KXP1843050617 | ||
| 035 | |a (OCoLC)1389826118 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Ambos-Spies, Klaus |d 1951- |e VerfasserIn |0 (DE-588)141551607 |0 (DE-627)629951861 |0 (DE-576)16006810X |4 aut | |
| 245 | 1 | 0 | |a Resource-bounded balanced genericity, stochasticity and weak randomness |c Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng |
| 264 | 1 | |c 1996 | |
| 300 | |a 12 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005 | ||
| 500 | |a Gesehen am 18.04.2023 | ||
| 520 | |a 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. | ||
| 533 | |a Reproduktion |f Lecture Notes in Computer Science | ||
| 650 | 4 | |a Complexity Theory | |
| 650 | 4 | |a Initial Segment | |
| 650 | 4 | |a Prediction Function | |
| 650 | 4 | |a Selection Function | |
| 650 | 4 | |a Weak Notion | |
| 700 | 1 | |a Mayordomo, Elvira |e VerfasserIn |0 (DE-588)1211678741 |0 (DE-627)1700308416 |4 aut | |
| 700 | 1 | |a Wang, Yongge |e VerfasserIn |0 (DE-588)1353449971 |0 (DE-627)1914768043 |4 aut | |
| 700 | 1 | |a Zheng, Xizhong |e VerfasserIn |0 (DE-588)1286451906 |0 (DE-627)1843052164 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a STACS (13 : 1996 : Grenoble) |t Proceedings |d Berlin [u.a.] : Springer, 1996 |g (1996), Seite 63-74 |h Online-Ressource (XII, 690 S.) |w (DE-627)595123015 |w (DE-576)9595123013 |z 9783540497233 |7 nnam |
| 773 | 1 | 8 | |g year:1996 |g pages:63-74 |g extent:12 |a Resource-bounded balanced genericity, stochasticity and weak randomness |
| 951 | |a AR | ||
| 992 | |a 20230418 | ||
| 993 | |a ConferencePaper | ||
| 994 | |a 1996 | ||
| 998 | |g 1353449971 |a Wang, Yongge |m 1353449971:Wang, Yongge |d 110000 |e 110000PW1353449971 |k 0/110000/ |p 3 | ||
| 998 | |g 141551607 |a Ambos-Spies, Klaus |m 141551607:Ambos-Spies, Klaus |d 110000 |d 110300 |e 110000PA141551607 |e 110300PA141551607 |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN1843050617 |e 4310879454 | ||
| BIB | |a Y | ||
| JSO | |a {"id":{"eki":["1843050617"],"doi":["10.1007/3-540-60922-9_6"]},"origin":[{"dateIssuedKey":"1996","dateIssuedDisp":"1996"}],"name":{"displayForm":["Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng"]},"relHost":[{"name":{"displayForm":["Claude Puech ... (eds.)"]},"id":{"isbn":["9783540497233"],"doi":["10.1007/3-540-60922-9"],"eki":["595123015"]},"origin":[{"publisherPlace":"Berlin [u.a.]","publisher":"Springer","dateIssuedKey":"1996","dateIssuedDisp":"1996"}],"physDesc":[{"extent":"Online-Ressource (XII, 690 S.)"}],"relMultPart":[{"title":[{"title":"Lecture notes in computer science","title_sort":"Lecture notes in computer science"}],"titleAlt":[{"title":"LNCS online"},{"title":"LNAI"},{"title":"Lecture notes in artificial intelligence"},{"title":"Lecture notes in bioinformatics"},{"title":"LNAI"},{"title":"LNBI"},{"title":"LNCS-LNAI"},{"title":"LNCS-LNBI"}],"part":{"number":["1046"],"number_sort":["104600"]},"pubHistory":["1.1973 -"],"recId":"316228877","language":["eng"],"disp":"Lecture notes in computer science","type":{"bibl":"serial","media":"Online-Ressource"},"note":["Gesehen am 28.02.20","Das Gesamtwerk gliedert sich in: Lecture notes in artificial intelligence; Lecture notes in bioinformatics"],"id":{"zdb":["2018930-8"],"eki":["316228877"],"issn":["1611-3349"]},"origin":[{"publisher":"Springer","dateIssuedKey":"1973","dateIssuedDisp":"1973-","publisherPlace":"Berlin ; Heidelberg"}],"dispAlt":"Lecture notes in computer science","physDesc":[{"extent":"Online-Ressource"}]}],"person":[{"role":"oth","display":"Puech, Claude","given":"Claude","family":"Puech"}],"title":[{"title_sort":"Proceedings / STACS 96","title":"Proceedings / STACS 96","subtitle":"13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22 - 24, 1996"}],"recId":"595123015","language":["eng"],"corporate":[{"role":"aut","display":"STACS (13, 1996, Grenoble)"}],"note":["Literaturangaben"],"disp":"STACS (13 : 1996 : Grenoble)Proceedings","type":{"bibl":"book","media":"Online-Ressource"},"part":{"year":"1996","pages":"63-74","text":"(1996), Seite 63-74","extent":"12"}}],"physDesc":[{"extent":"12 S."}],"title":[{"title":"Resource-bounded balanced genericity, stochasticity and weak randomness","title_sort":"Resource-bounded balanced genericity, stochasticity and weak randomness"}],"person":[{"given":"Klaus","family":"Ambos-Spies","role":"aut","roleDisplay":"VerfasserIn","display":"Ambos-Spies, Klaus"},{"display":"Mayordomo, Elvira","roleDisplay":"VerfasserIn","role":"aut","family":"Mayordomo","given":"Elvira"},{"family":"Wang","given":"Yongge","roleDisplay":"VerfasserIn","display":"Wang, Yongge","role":"aut"},{"roleDisplay":"VerfasserIn","display":"Zheng, Xizhong","role":"aut","family":"Zheng","given":"Xizhong"}],"recId":"1843050617","language":["eng"],"type":{"bibl":"chapter","media":"Online-Ressource"},"note":["Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005","Gesehen am 18.04.2023"]} | ||
| SRT | |a AMBOSSPIESRESOURCEBO1996 | ||