Geodesic
Andrei Al'bertovich Muchnik (obituary)
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 62 (2007) no. 4, pp. 775-779 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

@article{RM_2007_62_4_a5,
     author = {S. I. Adian and A. L. Semenov and V. A. Uspenskii},
     title = {Andrei {Al'bertovich} {Muchnik} (obituary)},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {775--779},
     year = {2007},
     volume = {62},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RM_2007_62_4_a5/}
}
TY  - JOUR
AU  - S. I. Adian
AU  - A. L. Semenov
AU  - V. A. Uspenskii
TI  - Andrei Al'bertovich Muchnik (obituary)
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2007
SP  - 775
EP  - 779
VL  - 62
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/RM_2007_62_4_a5/
LA  - en
ID  - RM_2007_62_4_a5
ER  - 
%0 Journal Article
%A S. I. Adian
%A A. L. Semenov
%A V. A. Uspenskii
%T Andrei Al'bertovich Muchnik (obituary)
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2007
%P 775-779
%V 62
%N 4
%U http://geodesic.mathdoc.fr/item/RM_2007_62_4_a5/
%G en
%F RM_2007_62_4_a5
S. I. Adian; A. L. Semenov; V. A. Uspenskii. Andrei Al'bertovich Muchnik (obituary). Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 62 (2007) no. 4, pp. 775-779. http://geodesic.mathdoc.fr/item/RM_2007_62_4_a5/

[1] Igry na beskonechnykh derevyakh i avtomaty s tupikami. Novoe dokazatelstvo razreshimosti monadicheskoi teorii dvukh sledovanii, Diplomnaya rabota, Kafedra matematicheskoi logiki, Mekh.-mat. f-t MGU, 1981; РЎРμмиотика Рё информатика, 24, Р’Р�РќР�РўР�, Рњ., 1985, 16–40 ; “Games on infinite trees and automata with dead-ends. A new proof for the decidability of the monadic second order theory of two successors”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 48 (1992), 220–267 | Zbl | Zbl

[2] “O teoreme Shyuttsenberzhe, kasayuscheisya monoidov bez netrivialnykh podgrupp”, Matematicheskaya logika, matematicheskaya lingvistika i teoriya algoritmov, Izd-vo Kalininskogo gos. un-ta, Kalinin, 1983, 65–68 | MR

[3] “Ob osnovnykh strukturakh deskriptivnoi teorii algoritmov”, Dokl. AN SSSR, 285:2 (1985), 280–283 | MR | Zbl

[4] Odno primenenie deistvitelnoznachnoi interpretatsii grammaticheskikh ryadov, In-t novykh tekhnologii, M., 1991; “One application of real-valued interpretation of formal power series”, Theoret. Comput. Sci., 290:3 (2003), 1931–1946 | DOI | MR | Zbl

[5] Vyrazimyi kriterii vyrazimosti v arifmetike Presburgera i ego primeneniya, In-t novykh tekhnologii, M., 1991; “The definable criterion for definability in Presburger arithmetic and its applications”, Theoret. Comput. Sci., 290:3 (2003), 1433–1444 | DOI | MR | Zbl

[6] “On common information”, Theoret. Comput. Sci., 207:2 (1998), 319–328 | DOI | MR | Zbl

[7] “Mathematical metaphysics of randomness”, Theoret. Comput. Sci., 207:2 (1998), 263–317 (with A. L. Semenov, V. A. Uspensky) | DOI | MR | Zbl

[8] “Conditional complexity and codes”, Theoret. Comput. Sci., 271:1–2 (2002), 97–109 | DOI | MR | Zbl

[9] “Upper semi-lattice of binary strings with the relation "$x$ is simple conditional to $y$”, Theoret. Comput. Sci., 271:1–2 (2002), 69–95 (with A. Chernov, A. Romashchenko, A. Shen, N. Vereshchagin) | DOI | MR | Zbl

[10] “Kolmogorov entropy in the context of computability theory”, Theoret. Comput. Sci., 271:1–2 (2002), 15–35 (with S. Ye. Positselsky) | DOI | MR | Zbl

[11] “An improvement of Kolmogorov's estimates related to random number generators and a definition of randomness in terms of complexity”, Dokl. Math., 68:1 (2003), 132–134 (with A. L. Semenov) | MR | Zbl

[12] “On the role of the law of large numbers in the theory of randomness”, Probl. Inf. Transm., 39:1 (2003), 119–147 (with A. L. Semenov) | DOI | MR | Zbl

[13] “40 Years of the origin of Kolmogorov randomness theory”, Kolmogorov i sovremennaya matematika. Tezisy dokladov Mezhdunar. konf., posv. 100-letiyu so dnya rozhd. A. N. Kolmogorova (25.04.1903–20.10.1987) (Moskva, 2003), Izd-vo mekh.-matem. f-ta MGU, M., 2003, 677–678 (with A. L. Semenovym)

[14] “Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets”, Ann. Pure Appl. Logic, 141:3 (2006), 437–441 (with A. Semenov) | DOI | MR | Zbl

[15] “Non-reducible descriptions for conditional Kolmogorov complexity”, Theory and applications of models of computation (Beijing, China, 2006), Lecture Notes in Comput. Sci., 3959, Springer, Berlin, 2006, 308–317 (with A. Shen, M. Ustinov, N. Vereshchagin, M. Vyugin) | MR | Zbl

[16] M. O. Rabin, “Decidability and definability in second-order theories”, Actes du Congrès international des mathématiciens (Nice, France, 1970), Vol. 1, Gauthier-Villars, Paris, 1971, 239–244 | MR | Zbl

[17] Y. Gurevich, L. Harrington, “Trees, automata, and games”, Proceedings of the fourteenth annual ACM symposium on theory of computing (San Francisco, USA, 1982), ACM Press, New York, 1982, 60–65 | MR

[18] A. L. Semenov, “Decidability of monadic theories”, Mathematical foundations of computer science (Prague, 1984), Lecture Notes in Comput. Sci., 176, Springer, Berlin, 1984, 162–175 | MR | Zbl

[19] A. Blumensath, S. Kreutzer, “An extension of Muchnik's theorem”, J. Logic Comput., 15:1 (2005), 59–74 | DOI | MR | Zbl

[20] A. Cobham, “On the base-dependence of set of numbers recognizable by finite automata”, Math. Systems Theory, 3:2 (1969), 186–192 | DOI | MR | Zbl

[21] A. L. Semënov, “Presburgerovost predikatov, regulyarnykh v dvukh sistemakh schisleniya”, Sib. matem. zhurn., 18:2 (1977), 403–418 | MR | Zbl

[22] A. L. Semënov, “Algoritmicheskie problemy dlya stepennykh ryadov i kontekstno-svobodnykh grammatik”, Dokl. AN SSSR, 212 (1973), 50–52 | MR | Zbl

[23] A. N. Kolmogorov, “On tables of random numbers”, Sankhyā Ser. A, 25 (1963), 369–376 ; Theoret. Comput. Sci., 207:2 (1998), 387–395 ; A. N. Kolmogorov, “O tablitsakh sluchainykh chisel”, Semiotika i informatika, 18, VINITI, M., 1982, 3–13 | MR | Zbl | DOI | MR | Zbl | MR | Zbl

[24] A. N. Kolmogorov, “K logicheskim osnovam teorii informatsii i teorii veroyatnostei”, Problemy peredachi informatsii, 5:3 (1969), 3–7 ; A. N. Kolmogorov, “Logical basis for information theory and probability theory”, IEEE Trans. Inform. Theory, 14:5 (1968), 662–664 | MR | Zbl | DOI | MR | Zbl