Страница памяти Андрея Мучника / Andrej Muchnik's Memorial Page

Список публикаций с дополнительной информацией

Файлы расположены в svn://adde.math.msu.su/shen/kolmbook
ссылки на них даны относительно kolmbook/muchnik-memorial/materials/publications/

Нет файлов для следующих работ (но есть файлы перевода или расширенной/сокращенной публикации):
inftrees:1982, cfgram:1985, cominf:1986, postprobl:1999, postprobl:1999e, postprobl:2001, postprobl:2001paris, kolmlogic:2001, kolmlogic:2001nov, Для нескольких работ есть отсканированный или скомпилированный файл, но нет исходного текста.



  1. Дипломная работа (видимо, текст не сохранился) inftrees:1982: Ан. А. Мучник. Игры на бесконечных деревьях и автоматы с тупиками. Новое доказательство разрешимости монадической теории двух следований. Кафедра математической логики механико-математического факультета МГУ им. М. В. Ломоносова, рукопись, 1982.
    Сохранились предварительные записи, сделанные Шенем по рассказам Андрея muchnik-diplom.djvu
    Включает в себя (1) доказательство теоремы об автоматности дополнения (2) алгоритм распознавания пустоты и (3) доказательство теоремы Макнотона о детерминизации автоматов на сверхсловах.
    inftrees:1985: Ан. А. Мучник. Игры на бесконечных деревьях и автоматы с тупиками. Новое доказательство разрешимости монадической теории двух следований. Семиотика и информатика, 24, том 24. 1985, с. 16-40. [MathSciNet]
    muchnik-semiotika24.djvu
    Впоследствии этот же текст (с некоторыми опечатками в нумерации теорем и лемм) был набран в TeXе. от чего сохранился лишь скан оттиска: muchnik-semiotika.djvu
    В дальнейшем этот текст был использован в диссертации Андрея.
    inftrees:1992: An. A. Muchnik. Games on Infinite Trees and Automata with Dead-Ends. A New Proof for the Decidability of the Monadic Second Order Theory of Two Successors. Bulletin of the European Association for Theoretical Computer Science, 1992, vol. 48, pp. 219-267.
    Muchnik1992InfiniteTrees.djvu отсканированный текст из EATCS
    Muchnik1992InfiniteTrees.pdf то же
    Muchnik1992InfiniteTrees.txt автоматически распознанный текст
    Перевод статьи в Семиотике и информатике. В переводе добавлено доказательство разрешимости проблемы пустоты. Есть файл с отрывком русского текста:
    TREE_NUM.TEX
    TREE_NUM.pdf
    Верещагин про него пишет следующее: "Его писал я на русском, затем его перевела на английский Яна Рышлинкова, и перевод вошел как первая часть в перевод работы inftrees:1985."
    Доказательство теоремы о детерминизации осталось лишь в рукописном начальном варианте; обобщение на случай ординальных автоматов (видимо, начавшееся с того же самого доказательства?) сохранилось среди неопубликованного: ver-ord-aut.tex
    ver-ord-aut.ps
    Ещё одна работа, обобщающая результаты Шелаха -- Ступа, не опубликована
    см. ниже monadtree
  2. schutzenberger:1983: Ан. А. Мучник. О теореме Шютценберже, касающейся моноидов без нетривиальных подгрупп. Математическая логика, математическая лингвистика и теория алгоритмов, Калинин, 1983, с. 65-68.
    Просканированный текст: muchnik-schutzenberger.djvu
  3. cfgram:1985: Ан. А. Мучник. Применение метода Семёнова к анализу структуры контекстно-свободных языков. Тезисы докладов и сообщений Всесоюзной школы-семинара "Семиотические аспекты формализации интеллектуальной деятельности. Кутаиси (Грузия)", Москва, 1985, сс. 212-214.
  4. cfgram:2003: An. A. Muchnik. One application of real-valued interpretation of formal power series. Theoretical Computer Science, 2003, vol. 290, pp. 1931-1946. [MathSciNet]
    Muchnik2003-1.pdf файл с сайта журнала
    muchnik-real-valued.tex окончательный текст, исправленный после рецензирования
    muchnik-real-value.tex исходный текст, посланный в журнал
    muchnik-real-value-p2.tex ранний вариант (получен от Ушакова)
    cfgram:1991: (препринт: Ан. А. Мучник. Одно применение действительно-значной интерпретации грамматических рядов. Москва: Институт новых технологий образования, 1991.)
    по тексту видно, что подготовлен в CW; скан:
    muchnik-cfgram.djvu
    следующий файл был перенесен с mac в мае 2002 (видимо, заново набранный текст препринта):
    GRAM_NUM.TEX
    GRAM_NUM.pdf
  5. alggame:1985: Ан. А. Мучник. Об основных структурах дескриптивной теории алгоритмов. Доклады АН СССР, т. 285, N 2, с. 280-283, 1985.
    muchnik-descriptive.djvu
    muchnik-descriptive.pdf Файлы содержат отсканированный оттиск (имеющийся у Шеня; видимо, текст готовил он)
    alggame:1985e: An. A. Muchnik. On the basic structures of the descriptive theory of algorithms. Soviet Mathematics Doklady, 1985, vol. 32, pp. 671-674. [MathSciNet]
    muchnik-descriptive-eng.pdf Отсканированная статья из журнала
  6. cominf:1986: Ан. А. Мучник. On the extraction of common information of two words. Первый всемирный конгресс Общества математической статистики и теории вероятностей имени Бернулли, Тезисы, Москва: Наука, 1986, т. 1, с. 453.
  7. cominf:1998: An. A. Muchnik. On common information. Theoretical Computer Science, 1998, vol. 207, pp. 319-328. [MathSciNet]
    muchnik-common-information.pdf файл с сайта журнала, есть оттиск
    muchnik-common-information.tex окончательный(?) исходный текст
  8. cominf:2002: A. Chernov, An. Muchnik, A. Romashchenko, A. Shen, N. Vereshchagin. Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theoretical Computer Science, 2002, vol. 271, nos. 1-2, pp. 69-95. [MathSciNet]
    Muchnik2002-2.pdf файл с сайта журнала
    muchnik-semilat.tex посланный в журнал файл
    cominf:1999: preliminary version: An. A. Muchnik, A. E. Romashchenko, N. K. Vereshchagin, A. Kh. Shen. Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Proceedings of 14th Annual IEEE Conference on Computational Complexity, Atlanta, USA, 1999, pp. 114-122.
    muchnik-semilat-atlanta.pdf
    cominf:1997: (preprint: DIMACS TR 97-74, Rutgers University, 1997) 97-74.ps
  9. limfreq:1987: Ан. А. Мучник. Нижние пределы частот в вычислимых последовательностях и релятивизованная априорная вероятность. Теория вероятностей и её применения, 1987, т. 32, N 3, с. 563-565.
    muchnik-freq.djvu
    muchnik-freq.pdf Файлы содержат отсканированный оттиск
    Статья, где объясняется, что нижние пределы частот в вычислимых последовательностях соответствуют 0'-перечислимым снизу полумерам (текст помогал готовить Шень)
    limfreq:1987e: An. A. Muchnik. Lower limits on frequences in computable sequences and relativized a priory probability. SIAM Theory Probab. Appl., 1987, vol. 32, pp. 513-514. [MathSciNet]
    muchnik-freq-eng.pdf отсканированная статья из журнала
    muchnik-freq-eng.djvu то же, с внедренным текстовым слоем
  10. limfreq:2008: Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Limit complexities revisited. STACS 2008 electronic proceedings, www.stacs-conf.org, pp.79-84.
    STACS-2008.tex
    STACS-2008.pdf Посланный на конференцию файл и pdf из трудов конференции.
  11. equa:1987: Ан. А. Мучник. Об одном классе полиномиальных систем уравнений, вытекающих из формулы полной вероятности, и возможности устранения перебора при их решении. Проблемы сокращения перебора, Вопросы кибернетики, 131, 1987, с. 180-195.
    eqv:1997: An. A. Muchnik. On a class of polynomial systems of equations following from the formula for total probability and possibilities for eliminating search in solving them. Problems of reducing the exhaustive search, 161-173, Amer. Math. Soc. Transl. Ser. 2, 178, Amer. Math. Soc., Providence, RI, 1997. Просканированный русский текст:
    muchnik-perebor.djvu
    английский eqv1997.pdf
  12. this:1988: Ан. А. Мучник, Л. С. Костюкова. Про ЭТО и про ТО. Тезисы школы-семинара по семиотическим аспектам формализации интеллектуальной деятельности, Боржоми (Грузия). Москва, 1988, с. 315-318.
    muchnik-this.djvu отсканированный текст рукописи с пометками Мучника
    muchnik-this.pdf
    muchnik-this.tex текст, перенабранный Шенем по рукописи
  13. netautom:1988: Ан. А. Мучник. О сильно универсальных сетях конечных автоматов. Девятая всесоюзная конференция по математической логике, Тезисы, 1988, с. 111.
    muchnik-netautom.djvu отсканированный текст из сборника
  14. bpp:1990: An. A. Muchnik. On the inclusion of the class BPP into the class Π2. Proceedings of European Summer Meeting of the Association for Symbolic Logic, Helsinki, 1990. The Journal of Symbolic Logic, 1991, vol. 56, no. 3, p. 1135. [gif]
    Muchnik1990.pdf получен из файла ../pritykin/files/Muchnik1990.gif
    Впоследствии выяснилось, что это рассуждение есть в C. Lautemann, BPP and the polynomial hierarchy, Inf. Proc. Letters, 14, 215-217 (1983).
  15. monad:1990: An. A. Muchnik, S. F. Soprunov. Decidability of monadic theories of countable structures and of their classes. Proceedings of European Summer Meeting of the Association for Symbolic Logic, Helsinki, 1990. The Journal of Symbolic Logic, 1991, vol. 56, no. 3, pp. 1146-1147. gif
    MuchnikSoprunov1990.pdf получен из файлов ../pritykin/files/MuchnikSoprunov1990-1.gif MuchnikSoprunov1990-2.gif
  16. infautom:1992: An. A. Muchnik, A.L. Semenov. Automata on infinite objects, monadic theories, and complexity. Abstract in "Automata Theory: Infinite Computations", Dagstuhl-Seminar-Report 28 (eds. K. Compton, J.-E. Pin, W. Thomas), 1992.
    muchnik-dagstuhl.tex набрано по сборнику
    muchnik-dagstuhl.pdf
    dagstuhl1992.pdf текст сборника
  17. oracles:1996: An. A. Muchnik, N. K. Vereshchagin. A General Method to Construct Oracles Realizing Given Relationships between Complexity Classes. Theoretical Computer Science, 1996, vol. 157, pp. 227-258. [MathSciNet]
    oracles.pdf файл с сайта журнала
    oracles:1994: extended version: University of Rochester, Technical Report 500, April 1994, pp. 1-49. Technical Report pdf файл из интернета
  18. random:1998: An. A. Muchnik, A. L. Semenov, V. A. Uspensky. Mathematical Metaphysics of Randomness. Theoretical Computer Science, 1998, vol. 207, pp. 263-317. [MathSciNet]
    muchnik-metaphysics.pdf файл с сайта журнала
    Следующие файлы на русском отражают разные этапы работы над текстом (они были перенесены с macintosh, поэтому есть ошибки, вызванные перекодированием):
    metaphysics1russ.pdf
    metaphysics1russ.tex Ан.А. Мучник, Игровой подход к определению случайности бесконечных последовательностей, 8 стр.
    metaphysics2russ.pdf
    metaphysics2russ.tex Математическая метафизика случайности, 3 стр. (только введение)
    metaphysics3russ.pdf
    metaphysics3russ.tex План, 8 стр., 15 пунктов с подпунктами
    metaphysics4russ.pdf
    metaphysics4russ.tex Случайность, 13 стр.
  19. random:2002moscow: An. A. Muchnik, A. L. Semenov. Correlations between randomness of finite sequences and stability of the frequences in simple subsequences. 2-nd Moscow-Vienna Workshop on Logic and Computation, Moscow, 26-27 April, 2002.
    muchnik-semenov-random-abstract-Moscow-Vienna.tex
    программа workshop'а, в файле после \end{document} следует резюме доклада, как оно было послано Яворскому 19.04.2002 (plain text) исходный вариант слайдов не сохранился - они были отредактированы для Logic Colloquium random:2002 (Чернов)
  20. random:2002: An. A. Muchnik, A. L. Semenov. Frequency and universal approaches to randomness of finite sequences. Logic Colloquium 2002, 3-9 August 2002, Muenster, Germany. The Bulletin of Symbolic Logic, Volume 9, 2003, p. 102.
    muchnik-semenov-random-abstract-Muenster.ps тезисы, опубликованные в BSL
    muchnik-semenov-random-abstract-Muenster.tex посланный на конференцию исходный текст
    muchnik-semenov-random-slides-Muenster.zip слайды доклада (tex-файлы)
    номер BSL с тезисами
  21. random:2003: Ан. А. Мучник, А. Л. Семенов. О роли закона больших чисел в теории случайности. Проблемы передачи информации, 2003, т. 39, N 1, сс. 134-165.
    muchnik-semenov-random-PPI-submitted.ps
    muchnik-semenov-random-PPI-submitted.tex посланный в журнал исходный текст muchnik-semenov-random-PPI-submitted.tex текст, опубликованный в журнале
    random:2003e: An. A. Muchnik, A. L. Semenov. On the Law of Large Numbers in Theory of Randomness. Problems of Information Transmission, 2003, vol. 39, N 1, pp. 119-147. [MathSciNet]
    muchnik-semenov-random-PIT.pdf файл из журнала, получен от Дм. Ногина вроде бы (Чернов)
    muchnik-semenov-random-PIT-submitted.tex исходный текст после окончательной правки
  22. random:2003dan: А. Л. Семенов, Ан. А. Мучник. Об уточнении оценок Колмогорова, относящихся к датчикам случайных чисел и сложностному определению случайности. Доклады Академии Наук, 2003, т. 391, N 6, сс. 738-740.
    muchnik-semenov-random-DAN.pdf окончательный файл, полученный из редакции
    muchnik-semenov-random-DAN-submitted.tex исходный текст
    muchnik-semenov-random-DAN-remark.tex примечание при корректуре
    random:2003danE: A. L. Semenov, An. A. Muchnik. An Improvement of Kolmogorov's Estimates Related to Random Number Generators and Definition of Randomness in Terms of Complexity. Doklady Mathematics, 2003, vol. 68, N 1, pp. 132-134. [MathSciNet]
    muchnik-semenov-random-DAN-eng.pdf окончательный журнальный текст
    muchnik-semenov-random-DAN-eng.txt текст (без формул), полученный из редакции
    muchnik-semenov-random-DAN-submitted-eng.tex исходный текст
    muchnik-semenov-random-DAN-remark-eng.tex примечание при корректуре
  23. random:2003kolm: An. A. Muchnik, A. L. Semenov. 40 years of the origin of Kolmogorov randomness theory. International conference "Kolmogorov and Contemporary Mathematics", June 16 - 21, 2003, Moscow, Russia.
    muchnik-semenov-random-abstract-Kolmogorov100.ps окончательный (?) текст тезисов (eng)
    muchnik-semenov-random-slides-Kolmogorov100.ps слайды доклада
    Расписание докладов
    muchnik-semenov-random-unpublished.tex
    muchnik-semenov-random-unpublished.pdf
    ещё один текст на эту тему, видимо, неопубликованный; кажется, новых теорем по сравнению с большой статьей в ППИ там нет, но как-то иначе построено изложение; как я помню, планировалось что-то опубликовать после конференции, но не знаю, чем это кончилось (Чернов)
    muchnik-semenov-random-unpublished-eng.tex частичный перевод на английский
  24. postprobl:1999: Ан. А. Мучник, С. Е. Посицельский. Об одном классе перечислимых множеств. Успехи математических наук, 1999, т. 54, N 3, с. 171-172.
    muchnik-posic-umn.pdf файл с сайта журнала
    postprobl:1999e: An. A. Muchnik, S. E. Positsel'skii. A class of enumerable sets. Russian Mathematical Surveys, vol. 54, N 3, pp. 640-641. [MathSciNet]
  25. postprobl:2001: Andrej A. Muchnik, Alexei L. Semenov. Single intermediate degrees in some classical reducibilities. Abstracts of International conference "Mathematical Logic, Algebra and Set Theory" dedicated to the 100-th anniversary of P. S. Novikov, Moscow, 2001, p. 33.
  26. postprobl:2001paris: An. A. Muchnik, A. L. Semenov. Entropies of finite objects help to define single intermediate degrees in some classical reducibilities. Proceedings of the International Workshop on "Logic and Complexity in Computer Science", Paris, 2001, pp. 195-197.
  27. postprobl:2002: Andrej A. Muchnik, Semen Ye. Positselsky. Kolmogorov entropy in the context of computability theory. Theoretical Computer Science, 2002, vol. 271, nos. 1-2, pp. 15-35. [MathSciNet]
    muchnik-posic-eng.pdf файл с сайта журнала
    muchnik-posic-eng.tex посланный в журнал исходный текст
    muchnik-posic-eng0.tex ранний вариант (получен от Ушакова)
    postprobl:1999pr: (preprint: Андрей А. Мучник, Семен Е. Посицельский. Колмогоровская энтропия с точки зрения общей теории алгоритмов Москва: Институт новых технологий образования, 1999.)
    У Шеня есть ксерокопия рукописи: её скан: muchnik-posic-manuscript.djvu
    и оттиск в зелёной обложке; его скан:
    muchnik-posic.djvu
    видно, что текст готовился в TeXе, но есть только совсем предварительный файл начала:
    muchnik-posic-rus.tex
    muchnik-posic-rus.pdf
  28. codes:2000: Andrej Muchnik, Alexej Semenov. Multi-conditional Descriptions and Codes in Kolmogorov Complexity. Electronic Colloquium on Computational Complexity, 2000, Report N 15. [ECCC Report TR00-15]
    muchnik-semenov-conditional.ps
    muchnik-semenov-conditional.pdf
    muchnik-semenov-conditional.tex исходный текст (получен от Ушакова)
  29. codes:2002: Andrej A. Muchnik. Conditional complexity and codes. Theoretical Computer Science, 2002, vol. 271, nos. 1-2, pp. 97-109.
    muchnik-conditional.pdf файл с сайта журнала
    muchnik-conditional.tex посланный в журнал исходный текст
    muchnik-conditional-rus.pdf русский текст (с которого переводился английский для журнала и нигде не публиковавшийся)
    muchnik-conditional-rus.tex исходный текст предыдущего
    muchnik-conditional-rus-shen.tex ранний вариант текста, написан Шенем (получен от Ушакова)
  30. diss:2001: Андрей Альбертович Мучник. Решение некоторых задач теории алгоритмов с использованием игровых методов. Диссертация на соискание учёной степени кандидата физико-математических наук, Москва: МГУ, 2001, 47 с. [ps]
    muchnik-disser.pdf
    muchnik-disser.ps текст диссертации без титульной страницы
    muchnik-disser.zip исходные файлы предварительного текста
    muchnik-disser2.zip исходные файлы окончательного(?) текста, включая автореферат
    diss-formalities.zip файлы разных бумаг для совета
  31. kolmlogic:2001eccc: Andrej A. Muchnik, Nikolai K. Vereshchagin. Logical operations and Kolmogorov complexity II.
    Electronic Colloquium on Computational Complexity, 2001, Report N 89. [ECCC Report TR01-89]
    muchnik-vereshchagin.pdf
    muchnik-vereshchagin.ps
    kolmlogic:2001: also in Proceedings of 16th Annual IEEE Conference on Computational Complexity, Chicago, June 2001, pp. 256-265.
  32. kolmlogic:2001nov: Andrej Muchnik, Alexander Shen, Nikolai Vereshchagin. Logical operations and Kolmogorov complexity. Abstracts of International conference "Mathematical Logic, Algebra and Set Theory" dedicated to the 100-th anniversary of P. S. Novikov, Moscow, 2001, p. 34.
  33. presburger:2003: An. A. Muchnik. The definable criterion for definability in Presburger arithmetic and its applications. Theoretical Computer Science, 2003, vol. 290, pp. 1433-1444. [MathSciNet]
    Muchnik2003-2.pdf файл с сайта журнала
    muchnik-expression.tex (предварительный?) файл перевода (Шень)
    muchnik-expression-p1.tex ранняя версия перевода (получен от Ушакова)
    presburger:1991: (preprint: Ан. А. Мучник. Выразимый критерий выразимости в арифметике Пресбургера и его применения Москва: Институт новых технологий образования, 1991.)
    У Шеня (помогавшего готовить текст) есть оттиск, видимо, подготовленный в CW, его скан:
    muchnik-samovyraz.djvu
  34. quasiperiod:2003: An. Muchnik, A. Semenov, M. Ushakov. Almost periodic sequences. Theoretical Computer Science, 2003, vol. 304, pp. 1-33. [MathSciNet]
    muchnik-semenov-ushakov3.ps окончательный текст (более окончательный, чем журнальный)
    muchnik-semenov-ushakov3.zip "Здесь исправлены многочисленные опечатки, которые остались в версии, отправленной в журнал в качестве окончательной."
    Almost_periodic_sequences.pdf файл с сайта журнала
    muchnik-semenov-ushakov.pdf
    muchnik-semenov-ushakov.zip исходный текст предварительного варианта
    muchnik-semenov-ushakov2.pdf
    muchnik-semenov-ushakov2.zip исходный текст окончательного текста, после рецензирования
  35. nonreduc:2004: A. Muchnik, A. Shen, N. Vereshchagin, M. Vyugin. Non-reducible descriptions for conditional Kolmogorov complexity. Electronic Colloquium on Computational Complexity, 2004, Report N 54. [ECCC Report TR04-054]
    muchnik-tamc2006-eccc.pdf
    muchnik-tamc2006-eccc.ps
  36. nonreduc:2006: Andrej Muchnik, Alexander Shen, Nikolai Vereshchagin, Michael Vyugin. Non-reducible descriptions for conditional Kolmogorov complexity. Proceedings of Third International Conference on Theory and Applications of Models of Computation (TAMC 2006, Beijing, China, May 15-20, 2006), Lecture Notes in Computer Science, vol. 3959, 2006, pp. 308-317.
    muchnik-tamc2006.pdf -- видимо, гранки из LNCS
    muchnik-tamc2006.zip -- исходные тексты для конференции
    Это напечатано в TCS (в расширенном виде, в числе авторов также М.Устинов):
    nonreducible-tcsreprint.pdf
    и имеются исходные тексты этого:
    muchnik-tamc2006-tcs.pdf
    muchnik-tamc2006-tcs.zip
    LNCS vol. contents
  37. predict:2004: A. Semenov, An. Muchnik. Methodology of predictions and their quality. Thesis of the 3rd international Moscow-Vienna Workshop on Logic and Computation, 2004.
    predictions-tezisy.ps тезисы доклада
    predictions.ps слайды доклада
    predictions-program.ps программа конференции
    predictions.zip исходные тексты См. также доклад experts:2006 и статью experts.
  38. eco:2004: Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin. Ecological Turing Machines. Proceedings of ICALP 2004, Lecture Notes in Computer Science, vol. 3142, 2004, pp. 457-468.
    Eco-ICALP-vere.ps окончательный или почти окончательный вариант для proceedings в ICALP
    Eco-ICALP-vere.tex исходный текст предыдущего (получен также от Верещагина)
    eco-2004-04-26.tex самый свежий из исходников (свежее, чем предыдущее)
    eco-rus.tex зачем-то переведённый на русский текст
    eco-slides.tex слайды для рассказа на ICALP (все файлы и пояснения получены от Ушакова)
  39. enum:2006: R. Biegel, H. Buhrman, P. Fejer, L. Fortnow, P. Grabowski, L. Longpre, A. Muchnik, F. Stephan, L. Torenvliet. Enumerations of the Kolmogorov Function. Journal of Symbolic Logic, 2006, vol. 71, N 2, pp. 501-528.
    enumerations.pdf файл с сайта Фортноу
    ../chernov/chernov4.rml история статьи и краткое содержание (Чернов)
    Идейно со статьей связан текст mutinf.
    enum:2004: (previous version in Electronic Colloquium on Computational Complexity, 2004, Report N 15 [ECCC Report TR04-15] ) [MathSciNet]
    muchnik-beigel.ps
    muchnik-beigel.pdf
  40. hypersimple:2006: An. Muchnik, A. Semenov. Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets. Annals of Pure and Applied Logic, 2006, vol. 141, N. 3, pp. 437-441. [pdf]
    MuchnikSemenov2006.pdf файл с сайта журнала
    hyper2006final.zip исходные тексты статьи
    hyper2006.zip разные предварительные варианты
    Есть неопубликованный расширенный текст hypersimple
  41. intuitgame:2006: An. A. Muchnik. On Game Interpretation of Intuitionistic Logic. Thesis of "Moscow Symposium on Logic, Algebra and Computation", dedicated to 75th birthday of academician S. I. Adian, 2006.
    Adian-75-eng.pdf вроде бы, самая поздняя версия слайдов
    Adian-75-slides.pdf еще версия слайдов
    Adian-75.ps слайды по-русски
    Adian-75.zip исходные тексты всего этого
  42. inequa:2006: An. Muchnik and N. Vereshchagin. Shannon Entropy vs. Kolmogorov Complexity. Proceedings of First International Computer Science Symposium in Russia (CSR 2006, St. Peterburg, Russia, June 2006), Lecture Notes in Computer Science, 2006, vol. 3967, pp. 281-291.
    shannon-vs-kolmogorov.ps файл с сайта Верещагина
    shannon-vs-kolmogorov.tex исходный текст (получен от Верещагина)
  43. solomon:2007: Marcus Hutter, Andrej Muchnik. On semimeasures predicting Martin-Löf random sequences. Theoretical Computer Science, to appear. [pdf] [doi:10.1016/j.tcs.2007.03.040]
    HutterMuchnik2007.pdf файл с сайта журнала
    solomon:2004: (previous version: M. Hutter, An. A. Muchnik. Universal Convergence of Semimeasures on Individual Random Sequences. Proceedings of the 15th International Conference on Algorithmic Learning Theory, LNAI, vol. 3244, 2004, pp. 234-248.)
    mlconvx.pdf
    mlconvx.tex файлы с сайта Хуттера
    ../chernov/chernov5.eml история статьи и краткое содержание (Чернов)
    mlconvx-2.zip одна из ранних версий статьи, zipped Postscript

Неопубликованные тексты и работы с неясным статусом

  1. crypto:2003: Alexei Semenov, Andrej Muchnik. Cryptography in the Context of Kolmogorov Entropy. Centennial Seminar on Kolmogorov Complexity and Applications, Dagstuhl Seminar 03181, Dagstuhl, Germany, 27.04 - 02.05.2003.
    Страница семинара, слайды на ней доступны.
    muchnik-crypt.ps
    muchnik-crypt.pdf
    muchnik-crypt.tex слайды доклада
    muchnik-crypt-remarks.ps
    muchnik-crypt-remarks.tex комментарии к слайдам
    На слайдах изложена схема доказательства.
    muchnik-crypto-romash.djvu записи, сделанные на докладе Мучника Андреем Ромащенко
    Muchnik-Cryptography.tex
    Muchnik-Cryptography-Shen.tex
    Muchnik-Cryptography-Shen.mp
    Muchnik-Cryptography-Shen.pdf Колмогоровская сложность и криптография
    Текст Чернова, затем частично переписанный Шенем, по мотивам конспекта колмогоровского семинара, восстановлены доказательства двух теорем из трёх.
  2. growth:2003: Andrej Muchnik and Alexei Semenov. A comparison of growths of simple and prefix entropies . Workshop on Computability and Randomness, Heidelberg, Germany, April 25 and 26, 2003.
    Страница конференции сейчас доступна только через webarchive.
    GROWTH.PS
    GROWTH.TEX слайды доклада
    GROWTH_C.PS
    GROWTH_C.TEX комментарии к слайдам
    Доклад посвящен доказательству т.Соловея в форме KS(x)<KP(x)-KP(KP(x))+2KP(KP(KP(x)))+O(1). В будущей книге Hirschfeldt, Downey, Algorithmic Randomness and Complexity лемма 7.2.5 - более сильный результат, без множителя 2.
  3. hypersimple:2003: Alexei Semenov, Andrej Muchnik. Natural Examples of Simple and Hypersimple Sets. Second St.Petersburg Days of Logic and Computability, St.Petersburg, Russia, 24-26 August 2003.
    Страница конференции
    semenov-muchnik-hypersimple.htm abstract с сайта конференции
    semenov-muchnik-hypersimple.pdf
    semenov-muchnik-hypersimple.tex слайды доклада (заглавие изменено на Constructive series, descriptive complexity, simple and hypersimple sets)
    semenov-muchnik-hypersimple-remark.pdf
    semenov-muchnik-hypersimple-remark.tex текст, написанный перед конференцией (по-русски), видимо, послужил основой статьи hypersimple:2006.
  4. experts:2006: Andrej Muchnik, Alexei Semenov. Optimal Aggregation of Expert Advices. Kolmogorov Complexity and Applications, Dagstuhl Seminar 06051, Dagstuhl, Germany, 29.01 - 03.02.2006.
    Страница семинара
    dag2006slide.pdf слайды доклада
    Dag2006-eng.ps что-то вроде тезисов
    Dag2006-rus.ps что-то вроде тезисов по-русски
    Dag2006.zip исходные тексты разной степени готовности
    См. также доклад predict:2004 и статью experts.
  5. hypersimple: Ан. А. Мучник, А. Л. Семенов. Гипергиперпростые множества, возникающие при вычислимой аппроксимации сверху префиксной сложности. 9 стр.
    hh-simple.pdf
    hh_symple.zip
    Из аннотации: "При обсуждении ... на семинаре С. И. Адяна авторам были заданы вопросы, ответы на которые привели к настоящей работе, которая является продолжением статьи hypersimple:2006". В тексте также написано, что некоторые результаты были объявлены в hypersimple:2003. Текст незакончен, не хватает части доказательств. Имеющуюся редакцию, видимо, следует датировать 29.06.2006.
  6. experts: А. Л. Семенов, Ан. А. Мучник. Оптимальная обработка вероятностных прогнозов двух экспертов. 15 стр.
    predictor.pdf версия статьи, скомпилированная 27.06.2005
    predictor-edited.tex predictor-edited.pdf исправление по правке Андрея в рукописи внесено под руководством А.А.Мучника и приведение к компилируемому виду 24.05.2007 - Шень
    predictor.tex исходный текст
    predictor.zip ранние версии
    В одном из списков работ был пункт
    А.А.Мучник, А.Л.Семенов. О скорости сходимости вероятностных предсказаний в терминах расстояния Хеллингера. 18.02.2004 Семинар кафедры теории вероятностей механико-математического факультета МГУ. См. также доклады predict:2004 и experts:2006.
    letters.tex letters.pdf письма Мучника Хуттеру, содержат неопубликованные части статьи solomon:2007 и первоначальные наброски данной статьи.
  7. advers: Simple deterministic strategy for Adversary in prediction with expert advice. 1 стр.
    experts.pdf, experts.tex
    Было рассказано по телефону Чернову осенью 2005 года. Одна теорема, пока без контекста.
  8. infdist: М. В. Вьюгин, Ан. А. Мучник Информационное расстояние для сложных строк.
    vyugin-muchnik.tex
  9. mutinf: Ан. Мучник. О взаимной информации двоичного слова и его энтропии. 8 стр.
    muchnik-on-mutual-rus.pdf
    muchnik-on-mutual-rus.tex
    Текст был подготовлен к публикации, но задержан до выхода статьи enum:2006; результаты докладывались на колмогоровском семинаре и семинаре Адяна.
    mutinfE: An. Muchnik. On mutual information of a binary word and its entropy.
    muchnik-on-mutual.pdf
    muchnik-on-mutual.tex перевод на английский, просмотренный Мучником (Чернов)
  10. perehod: Ан. Мучник. О сложности перехода от перечислимого задания конечной структуры к её явному заданию. 3 стр.
    muchnik-o-slozhnosti.pdf
    muchnik-o-slozhnosti.tex
    4 стр., указано, что задача поставлена Ромащенко
  11. ordaut: Ан. Мучник. Детерминизация ординальных автоматов. 15 стр.
    ORD_AUT.pdf
    ORD_AUT.TEX
    Теорема: Для любого ординального автомата $\cal A$ существует детерминированный ординальный автомат $\cal B$, $\rho $-эквивалентный $\cal A$ для всех счетных ординалов $\rho $. Автомат $\cal B$ можно построить по $\cal A$, причем количество состояний $\cal B$ есть $2^{2^{O(N)}}$, где $N$ --- количество состояний $\cal A$.
    Текст написан Верещагиным в конце 80-х.
    ver-ord-aut.tex
    ver-ord-aut.ps Переписанный Верещагиным (11-Oct-2008) текст.
  12. defrand: Ан. Мучник. Об определении случайности (название условное). 9 стр.
    ../chernov/chernov9.eml обсуждение смысла текста; сам результат, видимо, очень важен для попыток дать определение случайности относительно невычислимой меры (Чернов)
    Переработанный текст, написанный Черновым и Шенем, выложен в arxiv и послан в журнал ``Проблемы передачи информации'' в сентябре 2008 года. Файлы есть в supermartingales
    (включая файлы из архива, для ППИ и первоначальные версии)
  13. nesamov: Текст без заглавия, начинающаяся словами: ``ТЕОРЕМА. Двумерная модель действительных алгебраических чисел со сложением и умножением несамовыразима.'', 5 стр.
    muchnik-nesamov.pdf
    muchnik-nesamov.tex
  14. transduc: Текст без заглавия про finite transducers по мотивам Вебера, 22 стр.
    TRANSDUC.pdf
    TRANSDUC.TEX
    Тексты, подготовленные к печати Притыкиным и Горбуновым в 2008
    transducers.pdf
    transducers.ps
    transducers.tex
  15. monadtree: Текст без заглавия про монадические теории на деревьях, 10 стр.
    MONAD_TH.pdf
    MONAD_TH.TEX Начинается он с параграфа 4, очень похоже, что это не вставленный в диссертацию параграф, потому что 1 глава диссертации заканчивается 3-м параграфом, и все очень сходится (Притыкин)
    tree_str.pdf
    tree_str.tex английский перевод неизвестного происхождения
  16. autgame: Текст без заглавия, начинается "Напомним, что автоматной игрой с двумя игроками...", 4 стр.
    AUT_GAME.pdf
    AUT_GAME.TEX
    Содержит две теоремы:
    I. Любая автоматная игра является детерминированной, и по ней эффективно определяется, у какого игрока есть выигрышная стратегия.
    II. Существует алгоритм, который по любой автоматной игре $G$ решает вопрос о существовании минимального числа $n$ такого, что в игре $G(n)$ второй игрок имеет выигрышную стратегию и, если оно существует, находит это число. [В игре G(n) первый игрок указывает свои следующие n ходов, то есть на первом шаге первый игрок объявляет свои первые (n+1) ходов, второй --- свой первый ход, а на каждом следующем шаге каждый игрок добавляет 1 ход.]
    Горбунов видел его в начале 90-х.
  17. grgramm: Текст без заглавия про графовые грамматики, 27 стр.
    GRAPH_GR.pdf
    GRAPH_GR.TEX
    Горбунов пишет: "я записывал его примерно в 1990 году. Впоследствии выяснилось, что основная его теорема (про машины, работающие на графах) вроде бы следует (или эквивалентна) из какого-то результата Курселя (Bruno Courcelle), опубликованного им в серии работ про монадическую логику графов второго порядка (первая работа серии называется "The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs" и опубликована в 1990 г.) В связи с этим публикация текста была признана нецелесообразной (хотя на мой взгляд текст заслуживает публикации во-первых потому, что в работах Курселя разбираться сложно, а у Андрея всё изложено достаточно просто, а во-вторых текст содержит и другие интересные результаты, например, про NP-полноту задачи из теоремы Слисенко для несвязных графов)."
  18. relatkolm: Ан. А. Мучник, А. Ромащенко. Устойчивость колмогоровских свойств при релятивизации, 41 стр.
    muchnik-romash.pdf
    muchnik-romash.zip
  19. obzorkolm: Обзор результатов А. Л. Семёнова и Ан. А. Мучника, относящиеся к колмогоровской теории сложности
    obzor_kolm.pdf
    obzor_kolm.tex описаны работы random:1998, random:2003, random:2003dan, cominf:1998, codes:2002.
  20. philos: Андрей Мучник. Аннотация к статьям "Andreas Blass, Yuri Gurevich. Why Sets?" и "Cristian Calude, Elena Calude, Solomon Marcus. Passages of Proof", опубликованным в Bull. EATCS Oct. 2004
    Phil.pdf
    Phil.zip исходные файлы, включая раннюю версию.
    ../gurevich/beatcs84.pdf номер журнала с этими статьями
    В письме ../gurevich/gurevich.txt Юрий Гуревич пишет: "PPS. When I was last time in Moscow, Andrey Muchnik asked my permission to translate "Why Sets". I agreed of course. I presume that the matter is dead. All I want to say (for the whatever improbably case that the matter is not fully dead) that in the meantime we polished the paper; the polished version will appear in a Trakhtenbrot Festschrift."
  21. Последний рассказ Андрея записан в книге о колмогоровской сложности, appl-llll.tex (глава о приложениях колмогоровской сложности, запрещённые подпоследовательности, замечание в низу страницы 216) Там же (теорема 218 на с. 367) приводится конструкция контрпримера для всех выводимых формул без использования критических импликаций Медведева ЧСЧСЧС
    kolmbook.pdf
    (Шень)
  22. SEMENOV.pdf
    SEMENOV.TEX
    Набранный Черновым по просьбе Мучника текст "Упрощенное доказательство теоремы Тарского о разрешимости элементарной теории поля действительных чисел" Источником была, вроде бы, статья Семенов, А.Л., Разрешающие алгоритмы для логических теорий, Кибернетика и вычислительная техника, Москва: Наука, 1986, вып.2, с.134-146.
    Семенов пишет: "Что касается теоремы Тарского о разрешимости элементарной теории поля действительных чисел, то Мучник, действительно, это придумал. Я это много раз рассказывал в разных аудиториях и в некоторый момент написал текст с несколькими доказательствами разрешимости (для школьников и младшекурсников). Потом мы с Андреем (сейчас не помню последовательность событий) обнаружили, что у Коэна существует два доказательства. Одно, более легко доступное доказательство, в стиле Мучника, но сложнее. Но другое, которое мы нашли потом, почти дословно совпадает с Мучником (если я ничего не путаю). Поэтому, как изложение оригинального результата Мучника мой текст не подходит и включать его в составляемую сейчас библиографию не стоит."
    Шень добавляет: "Про доказательство теоремы Тарского - не знаю про Коэна, но один мой знакомый удивительным образом нашел ровно это доказательство в книге Хермандера (про эллиптические операторы, кажется), и я это показывал Андрею (который согласился, что там ну просто совсем то же самое)."
    Существует также текст Schoutens, Muchnik's proof of Tarski-Seidenberg, lecture notes.
Есть ещё написанный самим Андреем обзор его работ (auto-bio.txt), сначала английский (перевод в файле auto-bio-rus.txt), потом русский (с указанием планов), довольно давний, видимо. (Шень) Ещё лежат файлы al-a-muchnik1.djvu
Статья родителей Андрея Retro-temporal logic and finite automata
latex.preдля рисунков в метапосте
muchnik-files.htmlэтот файл
muchnik_papers.htmlсписок публикаций
raboty.texначальный план работ, составленный Семёновым
uspekhi-nekrolog.pdfнекролог в Успехах математических наук
ЧЧСЧС

На основную страницу the main page

© 20067 Колмогоровский семинар
Обратная связь