|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Большие системы
Устойчивость колмогоровских свойств при релятивизации
Ан. А. Мучник, А. Е. Ромащенкоa
a Институт проблем передачи информации им. А. А. Харкевича РАН
Аннотация:
Предположим, что кортеж слов $\bar a=\langle a_1,…,a_n\rangle$ имеет пренебрежимо малую взаимную информацию с некоторым словом $b$. Значит ли это, что свойства колмогоровской сложности набора слов $\bar a$ мало меняются при релятивизации относительно $b$? Если аккуратно формализовать поставленный вопрос, то окажется, что получить на него полный ответ очень непросто. В данной статье эта задача изучается для ограниченного класса свойств (для свойств, выразимых на языке $\exists$-формул). В частности, доказывается, что случайный относительно $\bar a$ оракул $b$ не помогает выделять общую информацию из слов $a_i$.
 Полный текст:
PDF файл (373 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Problems of Information Transmission, 2010, 46:1, 38–61
Реферативные базы данных:
   
Тип публикации:
Статья
УДК:
621.391.1+519.2
Поступила в редакцию: 08.06.2009
После переработки: 15.01.2010
Образец цитирования:
Ан. А. Мучник, А. Е. Ромащенко, “Устойчивость колмогоровских свойств при релятивизации”, Пробл. передачи информ., 46:1 (2010), 42–67; Problems Inform. Transmission, 46:1 (2010), 38–61
Цитирование в формате AMSBIB
\RBibitem{MucRom10}
\by Ан.~А.~Мучник, А.~Е.~Ромащенко
\paper Устойчивость колмогоровских свойств при релятивизации
\jour Пробл. передачи информ.
\yr 2010
\vol 46
\issue 1
\pages 42--67
\mathnet{http://mi.mathnet.ru/ppi2009}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2675298}
\elib{https://elibrary.ru/item.asp?id=15332059}
\transl
\jour Problems Inform. Transmission
\yr 2010
\vol 46
\issue 1
\pages 38--61
\crossref{https://doi.org/10.1134/S0032946010010059}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000276978000005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77951617221}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/ppi2009 http://mi.mathnet.ru/rus/ppi/v46/i1/p42
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Kaced T., Romashchenko A., “On essentially conditional information inequalities”, 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), 2011
-
Vereshchagin N., Shen A., “Algorithmic Statistics: Forty Years Later”, Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60Th Birthday, Lecture Notes in Computer Science, 10010, eds. Day A., Fellows M., Greenberg N., Khoussainov B., Melnikov A., Rosamond F., Springer International Publishing Ag, 2017, 669–737
 -
Romashchenko A. Zimand M., “An Operational Characterization of Mutual Information in Algorithmic Information Theory”, J. ACM, 66:5 (2019), 38
|
| Просмотров: |
| Эта страница: | 337 | | Полный текст: | 85 | | Литература: | 26 | | Первая стр.: | 6 |
|
Пользовательское соглашение