Priority method and separation problems. Метод приоритета и
проблемы отделения
- Doklady AN SSSR,
1979, 248, 6, 1309--1313. (Russian)
MR81b:03046
pdf
djvu
english translation (by author)
An axiomatic approach to algorithms theory and relativised
computability.
Аксиоматический подход к теории алгоритмов
и относительная вычислимость
- Vestnik MGU, ser. 1, 1980, 2, 27--29. (Russian)
MR 82b:03087
pdf
djvu
Some remark on non-integer numberings.
Некоторые замечания о нумерациях, не являющихся
натуральными
- Matematicheskaja logika
i matematicheskaja lingvistika. Kalinin, 1981. P. 162--165. (Russian)
MR 83k:03057
pdf
ps
djvu
Axiomatic description of the entropy notion for finite objects.
Аксиоматическое описания понятия энтропии для конечных объектов
VIII All-USSR conference ``Logika i metodologija nauki'',
Vilnjus, 1982, p. 104--105. (Russian)
pdf
ps
djvu
The problem calculus and f0-spaces.
Исчисление задач и f0-пространства
VI All-USSR Conference on
Math. Logic, Abstracts, Tbilisi, 1982, p. 204. (Russian)
pdf
ps
djvu
The frequency approach to the notion of random sequence.
Частотный подход к определению понятия случайной последовательности.
- Semiotika i informatika, M.:VINITI, 1982, 18, p. 14--42. (Russian)
pdf
ps
djvu
Понятие (&alpha,&beta)-стохастичности по Колмогорову и его свойства
Доклады Академии наук СССР, 271(6), 1337-1340.
pdf
ps
djvu
English translation:
The concept of
(&alpha,&beta)-stochasticity in the Kolmogorov sense, and its
properties.
Soviet Math. Dokl., vol. 28 (1983), no.1, p.295--299.
MR 85e:68034
pdf
ps
djvu
Towards the logical foundation of the applications of
Probability Theory.
К логические основаниям применений теории вероятностей.
--- Semioticheskie aspekty formalizatsii
intellektualnoi dejatelnosti, M., 1983, p.144-146 (Russian)
What is randomness?
Что такое случайность?
Квант, 1983, 7,.37-38. (Russian)
pdf
ps
djvu
Алгоритмические варианты понятия энтропии.
--- Doklady AN SSSR, 1984, 276, 3, 563--566. (Russian)
pdf
ps
djvu
English translation:
Algorithmic variants of the notion of entropy
Soviet Math. Dokl, Vol. 29 (1984), no.3, p.569-573,
MR 86f:94023
pdf
ps
djvu
Algorithmic variants of the notion of entropy. Ph.D. thesis.
Алгоритмические варианты понятия энтропии. Диссертация на
соискание учёной степени кандидата физико-математических наук.
Москва, 1985. (Russian)
pdf
Abstrast. Автореферат (Russian)
pdf
ps
djvu
One more definition of random sequence with respect to
computable measure.
- First World Congress of the Bernoulli
Society on Math. Statictics and Probability theory, Tashkent,
1986
L.L.Kontsevich, M.L.Kontsevich, A.Shen. Two algorithms of shape
reconstruction.
- Avtometrija, 1987, 5, p. 72--77.
(Russian)
English translation: Optoelectronics,
instrumentation and data processing, 1987, no. 5, pp. 76--81
Commentary to Kolmogorov's paper on randomness. (Russian)
- In:
A.N.Kolmogorov. Information theory and Algorithms Theory
(Selected Papers) M., Nauka, 1987.
MR 89a:01004
Computer Science (Informatika) in 9th grade of high school (Russian)
Informatika i Obrazovanie, 1987 (4), p. 20--30, (5), p. 24--31,
(6), p. 17--27, 1988, (1), p. 8--15.
pdf
ps
djvu
Kogan A.G., Shen A. Teaching Programming in Mathematics School,
- In: Isuchenie osnov informatiki i vychislitelnoi techniki v
srednei shkole, M., Prosvetschenie, 1987. (Russian)
Identity. Mathematical logic. (Articles for ``Small Mathematics Dictionary for children'')
Вероятностные стратегии в конечных играх с полной информацией.
- Теория вероятностей и её применения, 1987, 32, N 3, с. 567--569
Probabilistic strategies in games with full information.
- Theory of Probabilities and Its Applications, 1987, 32, N.3,
p.567--569. (in Russian) MR 88m:90170
pdf
ps
djvu
A.P.Erschov, A.G.Kushnirenko, G.V.Lebedev, A.L.Semenov, A.Shen. Computer Literacy (Informatik). A textbook for high schools. Moscow, 1988
О соотношении между различными алгоритмическими определениями случайности.
- Доклады АН СССР, 1988, 302, 3, 548--552.
pdf
djvu
Translation:
On relations between different algorithmic definitions of
randomness.
Soviet Math. Dokl., 38 (1989), 2, 316--319.
MR 90c:68034
pdf
djvu
Several chapters in "Programming: Simple and Difficult",
Moscow, 1988
(With A.L.Semenov, A.G.Kogan a.o.)
Editor of the Russian translation (by N.Vereshchagin) of
Paul Vitanyi and Ming Li paper "Kolmogorov complexity:
twenty years later"
djvu
В.А.Успенский, А.Л.Семёнов, А.Шень,
Может ли индивидуальная последовательность нулей и единиц быть
случайной?
- Успехи математических наук, 1990, 45(1), 105--162.
pdf
djvu
Translation:
V.A.Uspensky, A.L.Semenov, A.Shen. Can a single sequence of
zeros and ones be random?
Russian Math. Surveys, 45:1 (1990), 121--189.
MR 91f:03043
pdf
djvu
Algorithmic complexity and randomness: recent developments.
Second Congress of the Bernoulli Society.
(Invited talk on the Second Congress of Bernoulli
Society.)
Russian translation: Алгоритмическая сложность
и случайность: недавние достижения.
Теория вероятностей и её применения, 1992, 37(1),
124--131. MR1211211
djvu
Abstract of the talk.
pdf
ps
djvu
Patent: A device for checking the topology of connectors on a printed circuit (with coauthors) Moscow, 10 April, 1991.
IP=PSPACE: simplified proof.
Journal of the ACM, 39, no.4 (Oct. 1992), p. 878--880.
MR 94j:68270
pdf
[with A.K.Zvonkin, A.L.Semenov, S.K.Lando]
Algorithmics. Book for High School students
(Russian) Institute of New
Technologies, Moscow, 1992--1994. Reprinted later by "Drofa"
publishing house (without permission)
Kolmogorov Complexity.
- Lecture Notes, Pereslavl, 1992.
tex
Анти-Тьюринг, или должна ли машина мыслить?
Научно-техническая информация, серия 2.
Информационные процессы и системы. 1992, 3, p. 17--19.
djvu
Translated in: Automatic documentation and
Mathematical linguistics (1992),
v. 26, no. 2, pp. 9--12.
Gelfand I.M., Shen A. Algebra (Textbook).
Birkhauser, 1993, 2nd printing, 1995, 3rd printing, 2000,
4th printing, 2002, 5th printing, 2003, 6th printing, 2004.
Русский вариант:
Гельфанд И.М., Шень А. Алгебра. (Книга для школьников)
Москва. МЦНМО, 2-е изд., 2009
pdf
Comments to Kolmogorov's papers in: Kolmogorov A.N., Selected works of A.N.Kolmogorov, Vol.III. Edited by A.N.Shiryayev, translated from 1987 Russian original by A.B.Sossinsky, Kluwer Acad. Publ., Dordrecht, 1993 MR 95c:68096
Uspensky V.A., Shen A., Relations between varieties of
Kolmogorov complexities.
Tech. Report CS-R9329, CWI,
Netherlands, 1993
Final version: Math. Systems Theory, 29
(1996), N3, 271--292.
MR 97c:68074
pdf
D.Hammer, A.Shen. A Strange Application of Kolmogorov Complexity.
Theory of Computing Systems, 31 (1998), no.1, 1--4.
MR 99b:68103, Springer view link
(See also Tech.\
Report CS-R9328, CWI, Netherlands, 1993.)
pdf
K.Friedl, Z.Hatsagi, A.Shen, Low-degree tests
- Proc. of the
Fifth ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994),
ACM, New York, 1994, p. 57--64.
MR 95d:68055
pdf
djvu
Shen' A., Entrance examination to the Mekh-Math,
Math.Intelligencer, 16 (1994), no.4, 6-10. MR 1294993
pdf
Программирование: теоремы и задачи.
Частично опубликован в журнале
"Информатика и образование" в 1994 году. Первое издание: МЦНМО, 1995.
Второе издание, исправленное и дополненное: МЦНМО, 2004.
Третье издание: МЦНМО, 2007.
pdf
English version: "Algorithms and Programming: Problems and Solutions"
published by Birkhauser in 1997. 2nd ed. 2008 (Modern Classics,
Birkhauser), 3rd ed. 2009 (Springer).
Semiinteger rectangles; Cube and Tetrahedron.
Math. Intelligencer, 19 (1997), no.1, p. 12-14.
pdf
Three-dimensional solutions for two-dimensional problems.
Math. Intelligencer, 19 (1997), no.3, 44-47; MR1475148
pdf
An unfair game. Colorings and coverings. Tilings and
Polyhedra revisited.
Math. Intelligencer, 19 (1997), no.4, p. 48--50.
pdf
Probabilistic proofs
Math. Intelligencer, 20 (1998), no.3, 29--31, MR1646581
pdf
Two more probabilistic arguments. Poncelet theorem revisited.
Math. Intelligencer, 20 (1998), no.4, p. 30--32.
pdf
D.Hammer, A.Romashenko, A.Shen, N.Vereshchagin, Inequalities
for Shannon entropies and Kolmogorov complexities.
Proceedings
of Twelfth Annual IEEE Conference on Computational Complexity
(Ulm, 1997). P.13--23. IEEE Computer Soc., Los Alamitos, CA, 1997.
MR1758118.
Final version: Inequalities for
Shannon entropy and Kolmogorov Complexity, Journal of Computer
ans System Sciences, 2000, v.60, no.2, p.442--464; MR 2002e:68045
pdf
An.Muchnik, A.Romashchenko, N.Vereshagin, A.Shen, Upper
semi-lattice of binary strings with relation "x is simple
conditional to y".
DIMACS Tech. Report., 97-74 (December
1997)
Revised version: proceedings of 1999 Computational
Complexity conference (Atlanta, GA, 1999), 114-122, IEEE
Computer Soc., Los Alamitos, CA, 1999; MR1824585
Final version (with A. Chernov): TCS 271 (1--2), p. 69--95
(2002). MR: 2002m:68052
ps
pdf
B.Durand, A.Shen, N.Vereshagin. Descriptive Complexity of
Computable Sequences.
Proceedings of STACS'99 (Trier), Lecture notes in
Computer Science, 1563, pp. 153--162, 1999. MR2000i:68080
ECCC-087, 2001;
Theoretical Computer Science, 271 (no. 1--2), p. 47--58 (2002);
MR 2002k:68076
pdf
Unexpected proofs.
Math. Intelligencer, 21 (1999), no.3, p. 48--50.
pdf
Discussion on Kolmogorov Complexity and Statistical Analysis.
The Computer Journal, Vol. 42, No. 4, 1999, p. 340--342.
pdf
ps
Lecture notes: Algorithmic Information Theory and Kolmogorov Complexity,
Uppsala University Technical Report 2000-034, December 2000.
http://www.it.uu.se/research/reports/2000-034.
pdf
Н.К.Верещагин, А.Шень. Лекции по математической логике и теории
алгоритмов. Часть 1. Начала теории множеств.
М. МЦНМО. 2008 (3-е изд.)
pdf
English version: N.Vereshchagin, A.Shen. Basic set theory.
Published by AMS, 2002.
MR 2003f:03001
Н.К.Верещагин, А.Шень. Лекции по математической логике и теории
алгоритмов. Часть 2. Языки и исчисления.
(Part II. Languages and calculi. In Russian.)
М. МЦНМО. 2008 (3-е изд.)
pdf
Н.К.Верещагин, А.Шень. Лекции по математической логике и теории
алгоритмов. Часть 3. Вычислимые функции.
М. МЦНМО. 2008 (3-е изд.)
pdf
English version: N.Vereshchagin, A.Shen. Computable functions.
Published by AMS, 2003.
MR 2004b:03002
А.Китаев, М.Вялый, А.Шень. Классические и квантовые
вычисления.
М.:МЦНМО, 1999
ps
С исправлениями:
ps
English translation
by Lester J. Senechal:
A. Kitaev, M. Vyalyi, A. Shen. Classical and quantum
computations.
AMS, RI, 2002. NR2003e:81004
A Cultural Gap Revisited. Why Circles?
Math. Intelligencer, 22 (2000), no. 2, p. 16--18.
pdf
Lights Out.
Math. Intelligencer, 22 (2000), no. 3, p. 20--21.
pdf
Cliques, the Cauchy Inequality, and Information Theory.
Math. Intelligencer, 22 (2000), no. 4, p. 14--15.
pdf
Задачи по математике, предлагавшиеся ученикам математического класса
57 школы (выпуск 2000 года, класс В).
М.:МЦНМО, 2000.
pdf
ps
(Editor) Mathematical Problems Given to the Students of
57th Moscow School (graduated in 2000)
Moscow, MCCME
Publishers, 2000. (Russian)
A. Shen, N. Vereshchagin: Logical operations and Kolmogorov complexity
ECCC-088, 2001;
ps
pdf
Theoretical Computer Science, 271 (1--2), p. 125--129 (2002)
MR 2002k:68080
B.Durand, L.A.Levin, A.Shen. Complex tilings.
Proceedings of the
33rd Annual ACM STOC 2001, 732--739. MR:2120376
http://arxiv.org/ps/cs.CC/0107008
pdf
Journal of Symbolic Logic, 73 (2), 2007, p. 593--613.
A. Romashchenko, A. Shen, N. Vereshchagin, Combinatorial
interpretation of Kolmogorov complexity,
ECCC 7(26):2000;
15th
Annual IEEE conference on Computational Complexity (Florence,
2000), 131-137, IEEE Computer Soc., Los Alamitos, CA, 2000;
MR1823533.
pdf
TCS 271 (1--2): p. 111--123 (2002). MR 2003d:68104
Математическая индукция. М.:МЦНМО, 2004. 3-е изд., 2008
pdf
Mathematical induction. A popular exposition.
Moscow, MCCME publishers, 2004.
Логарифм и экспонента. М.:МЦНМО, 2005.
pdf
Logarithms and exponents. A popular exposition.
Moscow, MCCME publishers, 2005.
Простые и составные числа. М.:МЦНМО, 2005. 2-е изд., 2008
pdf
Prime and composite numbers.
Moscow, MCCME publishers, 2005.
Russian Encyclopedia. Articles on mathematical logic and computer science.
A.Muchnik, A.Shen, N.Vereshchagin, M.Vyugin.
Non-reducible descriptions for conditional Kolmogorov
complexity.
ECCC Report, TR04-054, Jun 29, 2004
See also: Theory and Applications of Models of Computation,
Lecture Notes in Computer Science,
Springer Berlin/Heidelberg,
3959 (2006), p.308-317
(a talk given in Beijing conference, May
2006). MR2277252
Extended version: Andrej Muchnik, Alexander Shen, Mikhail
Ustinov, Nikolai Vereshchagin, Michael Vyugin, Non-reducible
descriptions for conditional Kolmogorov complexity.
pdf
Theoretical
Computer Science, 2007, 384 (1), 77--86.
Universality in the theory of algorithms and computer science.
A talk given at Turing Days Conference, 2004, Istanbul.
pdf
B.Durand, L.A.Levin, A.Shen. Local rules and global order, or
Aperiodic Tilings.
Mathematical Intelligencer, 2005, v. 27, no.1, p. 64-68.
MR 2006c:52058
pdf
Noga Alon, Ilan Newman, Alexander Shen, Gabor Tardos,
Nikolai Vereshchagin.
Partitioning multi-dimensional sets in a
small number of ``uniform'' parts.
ECCC Report, TR05-95,
pdf
European Journal of Combinatorics, Volume 28, Issue 1, January
2007, p. 134--144. doi:10.1016/j.ejc.2005.08.002 MR2261810
Multisource information theory
ECCC Report, TR06-006.
Also published: Dagstuhl seminar 06051,
http://drops.dagstuhl.de/opus/volltexte/2006/626
pdf
See also: Theory and Applications of Models of Computation,
Lecture Notes in Computer Science, Springer Berlin/Heidelberg,
3959 (2006), p. 327-338. (a talk given in Beijing conference,
May 2006). MR2277254
talk slides (djvu)
Combinatorial proof of Muchnik's theorem.
Dagstuhl seminar 06051, http://drops.dagstuhl.de/opus/volltexte/2006/625
Extended version: D.Musatov, A.Romashchenko, A.Shen,
Variations on Muchnik's Conditional Complexity Theorem
Computer Science in Russia, 2009.
pdf
О "математической строгости" и школьном курсе математики.
М.:МЦНМО, 2006. 72с. ISBN 5-94057-254-5
A.Shen, "Mathematical rigour" and high-school
mathematics. (In Russian).
pdf
What is Kolmogorov complexity, talk on the biology workshop
organized by Poncelet Laboratory, 2006.
pdf
Игры и стратегии.
М.:МЦНМО, 2007. 2-е издание, 2008
Games and strategies (Russian).
pdf
Вероятность: примеры и задачи.
М.:МЦНМО, 2007. 2-е издание, 2008
Probability theory: Examples and Problems (Russian).
pdf
Laurent Bienvenu, Wolfgang Merkle, Alexander Shen. A simple
proof of Miller--Yu theorem.
pdf
Fundamenta Informaticae,
vol. 83, no. 1--2 (2008), p.21-24.
Laurent Bienvenu, Andrei Muchnik, Alexander Shen, Nikolay
Vereshchagin.
Limit complexities revisited.
Proceedings
of STACS 2008 conference, p.73-84,
http://drops.dagstuhl.de/opus/volltexte/2008/1335
pdf
Theory of Computing Systems, DOI 10.1007/s00224-009-9203-9, 17 March 2009.
Bruno Durand, Andrei Romashchenko, Alexander Shen. Fixed
Point and Aperiodic Tilings.
Proceedings of 12th
International Conference ``Developments in Language Theory''
(DLT), 2008, Lecture Notes in Computer in Science, vol. 5257,
Springer-Verlag, 2008. pp. 276-288.
HAL pdf
see also arXiv:0802.2432
Laurent Bienvenu, Andrei Romashchenko, Alexander Shen,
Sparse sets.
Journees Automates Cellulaires, 2008 (Uzes)
pp. 18--28.
HAL pdf
(Later M.Raskin showed that there are two computable measures that are
marginal distribution of some noncomputable measure, but are not marginal
distributions of any computable measure, answering the question posed
in the paper.)