Buchumschlag

Normalized information distance and the oscillation hierarchy

We study the complexity of computing the normalized information distance. We introduce a hierarchy of limit-computable functions by considering the number of oscillations. This is a function version of the difference hierarchy for sets. We show that the normalized information distance is not in any...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Ambos-Spies, Klaus (VerfasserIn) , Merkle, Wolfgang (VerfasserIn) , Terwijn, Sebastiaan A. (VerfasserIn)
Dokumenttyp: Article (Journal)
Sprache:Englisch
Veröffentlicht: 2022
In: Journal of computer and system sciences
Year: 2022, Jahrgang: 124, Pages: 65-76
ISSN:1090-2724
DOI:10.1016/j.jcss.2021.08.006
Online-Zugang:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.jcss.2021.08.006
Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/S0022000021000866
Volltext
Verfasserangaben:Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn

MARC

LEADER 00000caa a2200000 c 4500
001 1778007929
003 DE-627
005 20220820080902.0
007 cr uuu---uuuuu
008 211119s2022 xx |||||o 00| ||eng c
024 7 |a 10.1016/j.jcss.2021.08.006  |2 doi 
035 |a (DE-627)1778007929 
035 |a (DE-599)KXP1778007929 
035 |a (OCoLC)1341430870 
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 Normalized information distance and the oscillation hierarchy  |c Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn 
264 1 |c 2022 
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 Available online 24 September 2021 
500 |a Gesehen am 19.11.2021 
520 |a We study the complexity of computing the normalized information distance. We introduce a hierarchy of limit-computable functions by considering the number of oscillations. This is a function version of the difference hierarchy for sets. We show that the normalized information distance is not in any level of this hierarchy, strengthening previous nonapproximability results. As an ingredient to the proof, we demonstrate a conditional undecidability result about the independence of pairs of random strings. 
650 4 |a Independence 
650 4 |a Information distance 
650 4 |a Kolmogorov complexity 
700 1 |a Merkle, Wolfgang  |e VerfasserIn  |0 (DE-588)1049898400  |0 (DE-627)782852831  |0 (DE-576)40388201X  |4 aut 
700 1 |a Terwijn, Sebastiaan A.  |e VerfasserIn  |0 (DE-588)140769552  |0 (DE-627)703782266  |0 (DE-576)320698742  |4 aut 
773 0 8 |i Enthalten in  |t Journal of computer and system sciences  |d San Diego, Calif. [u.a.] : Elsevier, 1967  |g 124(2022) vom: März, Seite 65-76  |h Online-Ressource  |w (DE-627)26689254X  |w (DE-600)1469171-1  |w (DE-576)103373195  |x 1090-2724  |7 nnas  |a Normalized information distance and the oscillation hierarchy 
773 1 8 |g volume:124  |g year:2022  |g month:03  |g pages:65-76  |g extent:12  |a Normalized information distance and the oscillation hierarchy 
856 4 0 |u https://doi.org/10.1016/j.jcss.2021.08.006  |x Verlag  |x Resolving-System  |z lizenzpflichtig  |3 Volltext 
856 4 0 |u https://www.sciencedirect.com/science/article/pii/S0022000021000866  |x Verlag  |z lizenzpflichtig  |3 Volltext 
951 |a AR 
992 |a 20211119 
993 |a Article 
994 |a 2022 
998 |g 1049898400  |a Merkle, Wolfgang  |m 1049898400:Merkle, Wolfgang  |d 110000  |d 110300  |e 110000PM1049898400  |e 110300PM1049898400  |k 0/110000/  |k 1/110000/110300/  |p 2 
998 |g 141551607  |a Ambos-Spies, Klaus  |m 141551607:Ambos-Spies, Klaus  |d 110000  |e 110000PA141551607  |k 0/110000/  |p 1  |x j 
999 |a KXP-PPN1778007929  |e 4003653173 
BIB |a Y 
SER |a journal 
JSO |a {"language":["eng"],"recId":"1778007929","note":["Available online 24 September 2021","Gesehen am 19.11.2021"],"type":{"bibl":"article-journal","media":"Online-Ressource"},"title":[{"title_sort":"Normalized information distance and the oscillation hierarchy","title":"Normalized information distance and the oscillation hierarchy"}],"person":[{"given":"Klaus","family":"Ambos-Spies","role":"aut","roleDisplay":"VerfasserIn","display":"Ambos-Spies, Klaus"},{"role":"aut","display":"Merkle, Wolfgang","roleDisplay":"VerfasserIn","given":"Wolfgang","family":"Merkle"},{"given":"Sebastiaan A.","family":"Terwijn","role":"aut","roleDisplay":"VerfasserIn","display":"Terwijn, Sebastiaan A."}],"relHost":[{"title":[{"subtitle":"JCSS","title":"Journal of computer and system sciences","title_sort":"Journal of computer and system sciences"}],"disp":"Normalized information distance and the oscillation hierarchyJournal of computer and system sciences","note":["Gesehen am 04.06.2020"],"type":{"media":"Online-Ressource","bibl":"periodical"},"recId":"26689254X","language":["eng"],"pubHistory":["1.1967 -"],"part":{"year":"2022","pages":"65-76","volume":"124","text":"124(2022) vom: März, Seite 65-76","extent":"12"},"titleAlt":[{"title":"JCSS"}],"origin":[{"dateIssuedKey":"1967","publisher":"Elsevier ; Acad. Press ; Acad. Press","dateIssuedDisp":"1967-","publisherPlace":"San Diego, Calif. [u.a.] ; New York, NY [u.a.] ; San Diego, Calif. [u.a.]"}],"id":{"issn":["1090-2724"],"zdb":["1469171-1"],"eki":["26689254X"]},"physDesc":[{"extent":"Online-Ressource"}]}],"physDesc":[{"extent":"12 S."}],"id":{"doi":["10.1016/j.jcss.2021.08.006"],"eki":["1778007929"]},"origin":[{"dateIssuedKey":"2022","dateIssuedDisp":"2022"}],"name":{"displayForm":["Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn"]}} 
SRT |a AMBOSSPIESNORMALIZED2022 

Ähnliche Einträge