2012 |
Romashchenko A., Shen A., Durand B., B.Durand, A.Romashchenko, A.Shen. Fixed-point tile sets and their applications. Journal of Computer and System Sciences. Volume 78, Issue 3, May 2012, pp. 731-764.
Electronic version: arXiv:0802.2432v3 (2009), http://arxiv.org/abs/0910.2415 http://arxiv.org/abs/0910.2415
|
2011 |
Romashchenko A., Shen A., Musatov D.V., D.Musatov, A.Romashchenko, A.Shen. Variations on Muchnik"s Conditional Complexity Theorem. Theory Comput. Syst. 49 (2). 2011, pp. 227-245.
Electronic version: arXiv:0904.3116v4, http://arxiv.org/abs/0904.3116 http://arxiv.org/abs/0904.3116
|
2009 |
Durand B., Romashchenko A., Shen A., Fixed point theorem and aperiodic tilings, Bulletin of the European Association for Theoretical Computer Science (EATCS), no. 97, pp. 126-136 (The Logic in Computer Science Column by Yuri Gurevich) http://www.eatcs.org/images/bulletin/beatcs97.pdf
|
Durand B., Romashchenko A., Shen A., High Complexity Tilings with Sparse Errors. In Proceedings: Automata, Languages and Programming, 36th International Colloquium, (ICALP), Rhodes, Greece, July 5-12, 2009. Part I. Lecture Notes in Computer Science 5555 Springer 2009, pp. 403-414.
|
Musatov D., Romashchenko A., Shen A., Variations on Muchnik"s Conditional Complexity Theorem. Lecture Notes in Computer Science 5675: Proc. 4th International Computer Science Symposium in Russia (CSR). Novosibirsk, Russia, August 18-23, 2009. pp. 250-262. Electronic version: arXiv:0904.3116v2, http://arxiv.org/abs/0904.3116 http://arxiv.org/abs/0904.3116
|
Shen A., Algorithmic Information Theory and Foundations of Probability
Reachability Problems
Third International Workshop, RP 2009, Palaiseau, France, September 23-25, 2009, Proceedings
Lecture Notes in Computer Science
Vol. 5797
|
Bienvenu L., Shafer G., Shen A., On the history of martingales in the study of randomness,
Journal Elecronique d"Histoire des Probabilites et de la Statistique, ISSN 1773-0074.
|
Bienvenu L., Shen A., Algorithmic information theory and martingales. [A historic account]
arxiv 0906.2614
|
Chernov A., Shen A., Muchnik An., Algorithmic randomness and splitting of supermartingales,
arxiv 0807.3156
Проблемы передачи информации, 2009, 45:1, 60-70.
English version: Problems of Information Transmission, 2009, 45:1, 54-64.
|
Bienvenu L., Muchnik An., Shen A., Verehshchagin N., Limit complexities revisited. Proceedings of STACS 2008 conference, p.73-84, http://drops.dagstuhl.de/opus/volltexte/2008/1335
Theory of Computing Systems, DOI 10.1007/s00224-009-9203-9, 17 March 2009. http://drops.dagstuhl.de/opus/volltexte/2008/1335
|
2008 |
Durand B., Romashchenko A., Shen A., Fixed Point and Aperiodic Tilings. Lecture Notes in Computer Science 5257 Springer: Proc. 12th international conference on Developments in Language Theory (DLT). Kyoto, Japan, September 2008, pp. 537-548. Electronic version: arXiv:0802.2432v3. http://arxiv.org/abs/0802.2432
|
Bienvenu L., Romashchenko A., Shen A., Sparse sets. In Proc. First Symposium on Cellular Automata "Journees Automates Cellulaires" (JAC), Uzes, France, April 21-25, 2008, pp.18-28.
|
Vereshchagin N., Shen A., English version: N.Vereshchagin, A.Shen. Computable functions.
Published by AMS, 2003. MR 2004b:03002
|
Vereshchagin N., Shen A., English version: N.Vereshchagin, A.Shen. Basic set theory.
Published by AMS, 2002. MR 2003f:03001
|
Bienvenu L., Merkle W., Shen A., A simple proof of Miller--Yu theorem. Fundamenta Informaticae, vol. 83, no. 1--2 (2008), p.21-24.
|
Vovk V., Shen A., Prequential Randomness, Algorithmic Learning Theory, 19th International Conference (ALT 2008), Budapest, Hungary, Oct. 13--16, 2008, p.~154--168.
|
Chernov A., Shen A., Vereshchagin N., Vovk V., On-line Probability, Complexity and Randomness.
Algorithmic Learning Theory, 19th International Conference (ALT 2008), Budapest, Hungary, Oct. 13--16, 2008, Lecture Notes in Computer Science, v.~5254, p.~138--153.
|
2007 |
Shen A., Программирование: теоремы и задачи.
Третье издание: МЦНМО, 2007.
English version: "Algorithms and Programming: Problems and Solutions"
published by Birkhauser in 1997. 2nd ed. 2008 (Modern Classics, Birkhauser), 3rd ed. 2009 (Springer).
|
Alon N., Newman I., Shen A., Tardos G., Vereshchagin N., Partitioning multi-dimensional sets in a small number of ``uniform"" parts.
ECCC Report, TR05-95, European Journal of Combinatorics, Volume 28, Issue 1, January 2007, p. 134--144. doi:10.1016/j.ejc.2005.08.002 MR2261810
|
Shen A., 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.
Theoretical Computer Science, 2007, 384 (1), 77--86.
|
2006 |
Shen A., Multisource information theory
ECCC Report, TR06-006.
Also published: Dagstuhl seminar 06051, http://drops.dagstuhl.de/opus/volltexte/2006/626
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
|
2005 |
Shen A., 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
|
2002 |
Chernov A., Muchnik An., Shen A., Romashchenko A., Vereshchagin N., Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theoretical Computer Science. 271 (2002) pp. 69-95.
|
Romashchenko A., Shen A., Vereshchagin N., A.Romashchenko, A.Shen, N.Vereshchagin. Combinatorial Interpretation of Kolmogorov Complexity. Theoretical Computer Science. 271 (2002) pp. 111-123.
|
Shen A., Vereshchagin N., Logical operations and Kolmogorov complexity
ECCC-088, 2001;
Theoretical Computer Science, 271 (1--2), p. 125--129 (2002) MR 2002k:68080
|
Shen A., 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.
TCS 271 (1--2): p. 111--123 (2002). MR 2003d:68104
|
2000 |
Hammer D., Romashchenko A., Shen A., Vereshchagin N., D.Hammer, A.Romashchenko, A.Shen, N.Vereshchagin. Inequalities for Shannon Entropy and Kolmogorov Complexity. Journal of Computer and System Sciences. 60 (2000) pp. 442-464. http://www.mccme.ru/~anromash/ps/hrsv2000.ps
|
1999 |
Muchnik An., Romashchenko A., Shen A., Vereshchagin N., Muchnik An., Romashchenko A., Shen A., Vereshchagin N. Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 4-6 May 1999, Atlanta, Georgia, USA. IEEE Computer Society. 114-121.
|
1997 |
Hammer D., Romashchenko A., Shen A., Vereshchagin N., Hammer D., Romashchenko A., Shen A., Vereshchagin N. Inequalities for Shannon entropies and Kolmogorov complexities. Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, June 24-27, 1997, Ulm, Germany. IEEE Computer Society Press. pp. 13-23
|
1992 |
Shen A., IP=PSPACE: simplified proof.
Journal of the ACM, 39, no.4 (Oct. 1992), p. 878--880. MR 94j:68270
|
1990 |
Shen A., 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
|
1985 |
Shen A., Algorithmic variants of the notion of entropy. Ph.D. thesis.
|