DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2017.34

Another Characterization of the Higher K-Trivials

Authors: Paul-Elliot Anglès d'Auriac and Benoit Monin

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract

In algorithmic randomness, the class of K-trivial sets has proved itself to be remarkable, due to its numerous different characterizations. We pursue in this paper some work already initiated on K-trivials in the context of higher randomness. In particular we give here another characterization of the non hyperarithmetic higher K-trivial sets.

Cite as

Paul-Elliot Anglès d'Auriac and Benoit Monin. Another Characterization of the Higher K-Trivials. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{anglesdauriac_et_al:LIPIcs.MFCS.2017.34,
  author =	{Angl\`{e}s d'Auriac, Paul-Elliot and Monin, Benoit},
  title =	{{Another Characterization of the Higher K-Trivials}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.34},
  URN =		{urn:nbn:de:0030-drops-80837},
  doi =		{10.4230/LIPIcs.MFCS.2017.34},
  annote =	{Keywords: Algorithmic randomness, higher computability, K-triviality, effective descriptive set theory, Kolmogorov complexity}
}

Search Results

Documents authored by Anglès d'Auriac, Paul-Elliot

Another Characterization of the Higher K-Trivials

Abstract

Cite as

Thanks for your feedback!

Could not send message