Андрей Мучник: публикации / Andrei A. Muchnik: publications

  1. Ан. А. Мучник. Игры на бесконечных деревьях и автоматы с тупиками. Новое доказательство разрешимости монадической теории двух следований. Кафедра математической логики механико-математического факультета МГУ им. М. В. Ломоносова, рукопись, 1982.
    опубликовано: Семиотика и информатика, 24, 1985, с. 16-40. [MathSciNet]
    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.
  2. Ан. А. Мучник. О теореме Шютценберже, касающейся моноидов без нетривиальных подгрупп. Математическая логика, математическая лингвистика и теория алгоритмов, Калинин, 1983, с. 65-68.
  3. Ан. А. Мучник. Применение метода Семёнова к анализу структуры контекстно-свободных языков. Тезисы докладов и сообщений Всесоюзной школы-семинара "Семиотические аспекты формализации интеллектуальной деятельности. Кутаиси (Грузия)", Москва, 1985, сс. 212-214.
  4. Ан. А. Мучник. Об основных структурах дескриптивной теории алгоритмов. Доклады АН СССР, т. 285, N 2, с. 280-283, 1985.
    An. A. Muchnik. On the basic structures of the descriptive theory of algorithms. Soviet Mathematics Doklady, 1985, vol. 32, pp. 671-674. [MathSciNet]
  5. Ан. А. Мучник. On the extraction of common information of two words. Первый всемирный конгресс Общества математической статистики и теории вероятностей имени Бернулли, Тезисы, Москва: Наука, 1986, т. 1, с. 453.
  6. Ан. А. Мучник. Нижние пределы частот в вычислимых последовательностях и релятивизованная априорная вероятность. Теория вероятностей и её применения, 1987, т. 32, N 3, с. 563-565.
    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]
  7. Ан. А. Мучник. Об одном классе полиномиальных систем уравнений, вытекающих из формулы полной вероятности, и возможности устранения перебора при их решении. Проблемы сокращения перебора, Вопросы кибернетики, 131, 1987, с. 180-195.
    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.
  8. Ан. А. Мучник, Л. С. Костюкова. Про ЭТО и про ТО. Тезисы школы-семинара по семиотическим аспектам формализации интеллектуальной деятельности, Боржоми (Грузия). Москва, 1988, с. 315-318.
  9. Ан. А. Мучник. О сильно универсальных сетях конечных автоматов. Девятая всесоюзная конференция по математической логике, Тезисы, 1988, с. 111.
  10. 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. [pdf]
  11. 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. [pdf]
  12. 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.
  13. 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]
    extended version: University of Rochester, Technical Report 500, April 1994, pp. 1-49.
  14. An. A. Muchnik. On common information. Theoretical Computer Science, 1998, vol. 207, pp. 319-328. [MathSciNet]
  15. Aн. Мучник, Л. Переверзев, А. Семёнов. Мы узнали, что.... Компьютер в школе, 1999, номер 7, [pdf] (добавлено в 2020)
  16. An. A. Muchnik, A. L. Semenov, V. A. Uspensky. Mathematical Metaphysics of Randomness. Theoretical Computer Science, 1998, vol. 207, pp. 263-317. [MathSciNet]
  17. Ан. А. Мучник, С. Е. Посицельский. Об одном классе перечислимых множеств. Успехи математических наук, 1999, т. 54, N 3, с. 171-172.
    An. A. Muchnik, S. E. Positsel'skii. A class of enumerable sets. Russian Mathematical Surveys, vol. 54, N 3, pp. 640-641. [MathSciNet]
  18. 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]
  19. Андрей Альбертович Мучник. Решение некоторых задач теории алгоритмов с использованием игровых методов. Диссертация на соискание учёной степени кандидата физико-математических наук, Москва: МГУ, 2001, 47 с. [pdf]
  20. 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]
    also in Proceedings of 16th Annual IEEE Conference on Computational Complexity, Chicago, June 2001, pp. 256-265.
  21. 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.
  22. 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.
  23. 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.
  24. Andrej A. Muchnik. Conditional complexity and codes. Theoretical Computer Science, 2002, vol. 271, nos. 1-2, pp. 97-109.
  25. 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]
    (preprint: Андрей А. Мучник, Семен Е. Посицельский. Колмогоровская энтропия с точки зрения общей теории алгоритмов. Москва: Институт новых технологий образования, 1999.)
  26. 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]
    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.
    (preprint: DIMACS TR 97-74, Rutgers University, 1997)
  27. 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.
  28. 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.
  29. An. A. Muchnik. The definable criterion for definability in Presburger arithmetic and its applications. Theoretical Computer Science, 2003, vol. 290, pp. 1433-1444. [MathSciNet]
    (preprint: Ан. А. Мучник. Выразимый критерий выразимости в арифметике Пресбургера и его применения. Москва: Институт новых технологий образования, 1991.)
  30. An. A. Muchnik. One application of real-valued interpretation of formal power series. Theoretical Computer Science, 2003, vol. 290, pp. 1931-1946. [MathSciNet]
    (препринт: Ан. А. Мучник. Одно применение действительно-значной интерпретации грамматических рядов. Москва: Институт новых технологий образования, 1991.)
  31. Ан. А. Мучник, А. Л. Семенов. О роли закона больших чисел в теории случайности. Проблемы передачи информации, 2003, т. 39, N 1, сс. 134-165.
    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]
  32. А. Л. Семенов, Ан. А. Мучник. Об уточнении оценок Колмогорова, относящихся к датчикам случайных чисел и сложностному определению случайности. Доклады Академии Наук, 2003, т. 391, N 6, сс. 738-740.
    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]
  33. An. Muchnik, A. Semenov, M. Ushakov. Almost periodic sequences. Theoretical Computer Science, 2003, vol. 304, pp. 1-33. [MathSciNet]
  34. 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.
  35. 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]
  36. A. Semenov, An. Muchnik. Methodology of predictions and their quality. Thesis of the 3rd international Moscow-Vienna Workshop on Logic and Computation, 2004.
  37. 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.
  38. R. Beigel, 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.
    (previous version in Electronic Colloquium on Computational Complexity, 2004, Report N 15 [ECCC Report TR04-15] ) [MathSciNet]
  39. 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]
  40. 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.
  41. 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.
  42. 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.
  43. 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]
    (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.)
  44. Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai K. Vereshchagin, Michael V. Vyugin, Non-reducible descriptions for conditional Kolmogorov complexity. Theoretical Computer Science, 384(1), 77-86(2007), link (added in 2020)
  45. Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin. Limit compexities revisited. STACS 2008 electronic proceedings. [pdf]. See also: Theory Comput. Syst. 47(3): 720-736 (2010),
  46. Ан. А. Мучник, “Алгоритмическая случайность и разбиение супермартингалов”, Пробл. передачи информ., 45:1 (2009), 60–70; Andrej Muchnik (edited by Alexey V. Chernov, Alexander Shen). Algorithmic randomness and splitting of supermartingales, Probl. Inf. Transm. 45(1): 54-64 (2009), journal link arxiv (added in 2020)
  47. Andrei A. Muchnik, Andrei E. Romaschenko, A Random Oracle Does Not Help Extract the Mutual Information. MFCS 2008: 527-538, link (added in 2020)
  48. Андрей А. Мучник, Ю.Притыкин, А.Л.Семёнов. Последовательности, близкие к периодическим. УМН, 2009, том 64, выпуск 5(389), страницы 21–96, link [Andrei A. Muchnik, Yuri Pritykin, Alexei L. Semenov: Sequences close to periodic. In Russian. CoRR abs/0903.5316 (2009), arxiv] (added in 2020)
  49. Andrej Muchnik, Ilya Mezhirov, Alexander Shen, Nikolai K. Vereshchagin: Game interpretation of Kolmogorov complexity. CoRR abs/1003.4712 (2010), arxiv (added in 2020)
  50. Andrej A. Muchnik, Kolmogorov complexity and cryptography (2011), arxiv (russian+english) (added in 2020)
  51. Ан. А. Мучник, А.Е.Ромащенко, Устойчивость колмогоровских свойстви при релятивизации (Andrei A. Muchnik, Andrei E. Romashchenko: Stability of properties of Kolmogorov complexity under relativization). Probl. Inf. Transm. 46(1): 38-61 (2010), link (added in 2020)
  52. Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolai Vereshchagin, Limit complexities revisited [once more] (2012), arxiv (added in 2020)
  53. Andrej Muchnik, Alexander Shen, Mikhail Vyugin, Game arguments in computability theory and algorithmic information theory, arxiv (added in 2020)
  54. Ан. А. Мучник, “Детерминизация ординальных автоматов”, Пробл. передачи информ., 49:2 (2013), 58–72, link [An. A. Muchnik, “Determinization of ordinal automata”, Problems Inform. Transmission, 49:2 (2013), 149–162] (added in 2020)
  55. Ан. А. Мучник, К. Ю. Горбунов, Алгоритмические аспекты декомпозиции и эквивалентности конечнозначных преобразователей, Пробл. передачи информ., 2015, том 51, выпуск 3, страницы 70–92; Andrei A. Muchnik, Konstantin Yu. Gorbunov: Algorithmic aspects of decomposition and equivalence of finite-valued transducers. Probl. Inf. Transm. 51(3): 267-288 (2015) link (added in 2020)
  56. Ан. А. Мучник, А. Л. Семёнов, “Решетка определимости в порядке рациональных чисел”, Матем. заметки, 108:1 (2020), 102–118 [An. A. Muchnik, A. L. Semenov, “Lattice of Definability in the Order of Rational Numbers”, Math. Notes, 108:1 (2020), 94–107] link, pdf (added in 2020)