Schnorr Triviality and Its Equivalent Notions

Miyabe, Kenshi

Downloads: 213

http://hdl.handle.net/2433/198571

Files in This Item:

File	Description	Size	Format
s00224-013-9506-8.pdf		218.32 kB	Adobe PDF	View/Open

Full metadata record

DC Field	Value	Language
dc.contributor.author	Miyabe, Kenshi	en
dc.contributor.alternative	宮部, 賢志	ja
dc.date.accessioned	2015-06-26T06:43:46Z	-
dc.date.available	2015-06-26T06:43:46Z	-
dc.date.issued	2013-09-29	-
dc.identifier.issn	1432-4350	-
dc.identifier.uri	http://hdl.handle.net/2433/198571	-
dc.description.abstract	We give some characterizations of Schnorr triviality. In concrete terms, we introduce a reducibility related to decidable prefix-free machines and show the equivalence with Schnorr reducibility. We also give a uniform-Schnorr-randomness version of the equivalence of LR-reducibility and LK-reducibility. Finally we prove a base-type characterization of Schnorr triviality.	en
dc.format.mimetype	application/pdf	-
dc.language.iso	eng	-
dc.publisher	Springer US	en
dc.rights	The final publication is available at Springer via http://dx.doi.org/10.1007/s00224-013-9506-8	en
dc.rights	この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。	ja
dc.rights	This is not the published version. Please cite only the published version.	en
dc.subject	Algorithmic randomness	en
dc.subject	Schnorr randomness	en
dc.subject	Schnorr triviality	en
dc.subject	Uniform relativization	en
dc.title	Schnorr Triviality and Its Equivalent Notions	en
dc.type	journal article	-
dc.type.niitype	Journal Article	-
dc.identifier.ncid	AA11115134	-
dc.identifier.jtitle	Theory of Computing Systems	en
dc.identifier.volume	56	-
dc.identifier.issue	3	-
dc.identifier.spage	465	-
dc.identifier.epage	486	-
dc.relation.doi	10.1007/s00224-013-9506-8	-
dc.textversion	author	-
dc.startdate.bitstreamsavailable	2014-09-29	-
dcterms.accessRights	open access	-
Appears in Collections:	Journal Articles

Show simple item record

Export to RefWorks