Andrei A. Muchnik

Publication Activity (10 Years)

Years Active: 1996-2015
Publications (10 Years): 0

Top Topics

Finite Automata

Algorithmic Aspects

Top Venues

Probl. Inf. Transm.

Publications

Andrei A. Muchnik, Konstantin Yu. Gorbunov
Algorithmic aspects of decomposition and equivalence of finite-valued transducers. Probl. Inf. Transm. 51 (3) (2015)
Andrei A. Muchnik
Determinization of ordinal automata. Probl. Inf. Transm. 49 (2) (2013)
Andrei A. Muchnik, Andrei E. Romashchenko
Stability of properties of Kolmogorov complexity under relativization. Probl. Inf. Transm. 46 (1) (2010)
Andrei A. Muchnik
Algorithmic randomness and splitting of supermartingales. Probl. Inf. Transm. 45 (1) (2009)
Andrei A. Muchnik, Yuri Pritykin, Alexei L. Semenov
Sequences close to periodic CoRR (2009)
Andrei A. Muchnik, Andrei E. Romashchenko
A Random Oracle Does Not Help Extract the Mutual Information. MFCS (2008)
Andrei A. Muchnik, Nikolai K. Vereshchagin
Shannon Entropy vs. Kolmogorov Complexity. CSR (2006)
Andrei A. Muchnik, Alexander Shen, Nikolai K. Vereshchagin, Michael V. Vyugin
Non-reducible descriptions for conditional Kolmogorov complexity Electron. Colloquium Comput. Complex. (054) (2004)
Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin
Ecological Turing Machines. ICALP (2004)
Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet
Enumerations of the Kolmogorov Function Electron. Colloquium Comput. Complex. (015) (2004)
Andrei A. Muchnik
The definable criterion for definability in Presburger arithmetic and its applications. Theor. Comput. Sci. 290 (3) (2003)
Andrei A. Muchnik
One application of real-valued interpretation of formal power series. Theor. Comput. Sci. 290 (3) (2003)
Andrei A. Muchnik, Alexei L. Semenov, Maxim Ushakov
Almost periodic sequences. Theor. Comput. Sci. 304 (1-3) (2003)
Andrei A. Muchnik, Alexei L. Semenov
On the Role of the Law of Large Numbers in the Theory of Randomness. Probl. Inf. Transm. 39 (1) (2003)
Andrei A. Muchnik
Conditional complexity and codes. Theor. Comput. Sci. 271 (1-2) (2002)
Andrei A. Muchnik, Semen Ye. Positselsky
Kolmogorov entropy in the context of computability theory. Theor. Comput. Sci. 271 (1-2) (2002)
Alexey V. Chernov, Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theor. Comput. Sci. 271 (1-2) (2002)
Andrei A. Muchnik, Nikolai K. Vereshchagin
Logical operations and Kolmogorov complexity. II Electron. Colloquium Comput. Complex. (089) (2001)
Andrei A. Muchnik, Nikolai K. Vereshchagin
Logical Operations and Kolmogorov Complexity II. Computational Complexity Conference (2001)
Andrei A. Muchnik, Alexei L. Semenov
Multi-conditional Descriptions and Codes in Kolmogorov Complexity Electron. Colloquium Comput. Complex. 7 (15) (2000)
Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". Computational Complexity Conference (1999)
Andrei A. Muchnik, Alexei L. Semenov, Vladimir A. Uspensky
Mathematical Metaphysics of Randomness. Theor. Comput. Sci. 207 (2) (1998)
Andrei A. Muchnik
On Common Information. Theor. Comput. Sci. 207 (2) (1998)
Andrei A. Muchnik, Nikolai K. Vereshchagin
A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. Theor. Comput. Sci. 157 (2) (1996)