?
Plain stopping time and conditional complexities revisited
P. 1-24.
Пособин Г. И., Shen A., Andreev M.
Ключевые слова: Kolmogorov complexitystopping time complexitystructured conditional complexityalgorithmic information theory
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
В книге
Vol. 117. , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018
Верещагин Н. К., Баувенс Б. Ф., Makhlin A. и др., Computational Complexity 2018 Vol. 27 No. 1 P. 31-61
Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...
Добавлено: 22 апреля 2017 г.
Добавлено: 23 декабря 2022 г.
Сухов Ю. М., Кельберт М. Я., China Machine Press, 2017
Эта книга включает стандартный пакет информационно-теоретического материала, обычно читаемого на факультетахинформатики и электроники, а также прикладной математики, ведущих университетов, наряду с некоторыми новыми результатами. При этом излагаются как вероятнростные, так и алгебраические аспекты теории информации и кодирования, включая как основы теории, так и некоторые ее современные аспекты. Предмет этой книги критически важен для современных приложений ( телекоммуникации, ...
Добавлено: 8 мая 2021 г.
Баувенс Б. Ф., Блинников И. А., , in : Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings. Vol. 12159.: Springer, 2020. P. 130-141.
Добавлено: 5 февраля 2021 г.
Рубцов А. А., , in : Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. : Cham : Springer, 2018. P. 553-565.
Добавлено: 12 сентября 2018 г.
Баувенс Б. Ф., Theory of Computing Systems 2015 Vol. 58 No. 3 P. 482-501
Добавлено: 2 октября 2015 г.
Баувенс Б. Ф., Shen A., Journal of Symbolic Logic 2013 Vol. 79 No. 2 P. 620-632
Добавлено: 2 октября 2015 г.
Милованов А. С., Theory of Computing Systems 2017 Vol. 61 No. 2 P. 521-535
Algorithmic statistics is a part of algorithmic information theory (Kolmogorov complexity theory) that studies the following task: given a finite object x (say, a binary string), find an `explanation' for it, i.e., a simple finite set that contains x and where x is a `typical element'. Both notions (`simple' and `typical') are defined in terms ...
Добавлено: 27 июня 2016 г.
Баувенс Б. Ф., , in : 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1-46:14.
Добавлено: 20 марта 2020 г.
Bienvenu L., Muchnik A., Shen A. и др., / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.
Добавлено: 14 декабря 2013 г.
Баувенс Б. Ф., Archive for Mathematical Logic 2015 Vol. 54 No. 5 P. 615-629
Joseph Miller [16] and independently Andre Nies, Frank Stephan and Sebastiaan Terwijn [18] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity C: they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length). Later Miller [17] showed that prefix complexity K ...
Добавлено: 2 октября 2015 г.
Antunes L., Баувенс Б. Ф., Souto A. и др., Theory of Computing Systems 2017 Vol. 60 No. 2 P. 280-298
Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program ...
Добавлено: 4 мая 2016 г.
Bienvenu L., Desfontaines D., Shen A., Logical Methods in Computer Science 2016 Vol. 12 No. 2
The halting problem is undecidable --- but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the ...
Добавлено: 7 февраля 2017 г.
Bauwens B., Makhlin A., Верещагин Н. К. и др., / Hasso-Plattner-Institut. Series Technical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-007.
Добавлено: 14 декабря 2013 г.
Верещагин Н. К., Милованов А. С., , in : 32nd Computational Complexity Conference. : Вадерн : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1-18.
A fundamental notion in Algorithmic Statisticsis that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical ...
Добавлено: 12 октября 2017 г.
Верещагин Н. К., Shen A., Lecture Notes in Computer Science 2017 Vol. 10010 P. 669-737
Добавлено: 13 февраля 2017 г.
Милованов А. С., , in : Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017). Vol. 10304.: Luxemburg : Springer, 2017. P. 232-244.
Добавлено: 15 октября 2017 г.
Милованов А. С., , in : Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings. : Springer, 2021. Ch. 17. P. 283-295.
Добавлено: 11 августа 2021 г.
Милованов А. С., , in : 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) Leibniz International Proceedings in Informatics (LIPIcs). : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2016. Ch. 54. P. 1-13.
Добавлено: 27 июня 2016 г.
Добавлено: 12 октября 2017 г.
Shen A., Верещагин Н. К., , in : Computability and Complexity. : Berlin : Springer, 2017. P. 669-737.
Добавлено: 26 октября 2018 г.
Верещагин Н. К., Theoretical Computer Science 2023 Vol. 940 P. 108-122
Добавлено: 19 декабря 2022 г.
Милованов А. С., , in : Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015. Vol. 9139.: Springer, 2015. P. 339-349.
Добавлено: 27 июня 2016 г.