Alexander Shen

CoRR, 2012

Game Arguments in Computability Theory and Algorithmic Information Theory.

[BibT_eX]

[DOI]

Proceedings of the How the World Computes, 2012

Random Semicomputable Reals Revisited.

[BibT_eX]

[DOI]

Proceedings of the Computation, Physics and Beyond, 2012

2011

Not every domain of a plain decompressor contains the domain of a prefix-free one.

[BibT_eX]

[DOI]

Mikhail Andreev

Ilya P. Razenshteyn

Theor. Comput. Sci., 2011

Variations on Muchnik's Conditional Complexity Theorem.

[BibT_eX]

[DOI]

Daniil Musatov

Theory Comput. Syst., 2011

An additivity theorem for plain complexity

[BibT_eX]

[DOI]

Bruno Bauwens

CoRR, 2011

Are random axioms useful?

[BibT_eX]

[DOI]

CoRR, 2011

Algorithmic tests and randomness with respect to a class of measures

[BibT_eX]

[DOI]

CoRR, 2011

Kolmogorov Complexity as a Language.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Prequential randomness and probability.

[BibT_eX]

[DOI]

Vladimir Vovk

Theor. Comput. Sci., 2010

Limit Complexities Revisited.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Sets of k-Independent Strings.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2010

Game interpretation of Kolmogorov complexity

[BibT_eX]

[DOI]

Ilya Mezhirov

CoRR, 2010

Decomposition Complexity.

[BibT_eX]

[DOI]

Proceedings of the Second Symposium on Cellular Automata "Journées Automates Cellulaires", 2010

1D Effectively Closed Subshifts and 2D Tilings.

[BibT_eX]

[DOI]

Proceedings of the Second Symposium on Cellular Automata "Journées Automates Cellulaires", 2010

Ergodic-Type Characterizations of Algorithmic Randomness.

[BibT_eX]

[DOI]

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

Effective Closed Subshifts in 1D Can Be Implemented in 2D.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation, 2010

Algorithms and Programming - Problems and Solutions, Second Edition.

[BibT_eX]

[DOI]

Springer undergraduate texts in mathematics and technology, Springer, ISBN: 978-1-4419-1747-8, 2010

2009

Fixed Point Theorem and Aperiodic Tilings.

[BibT_eX]

Bull. EATCS, 2009

Algorithmic Information Theory and Foundations of Probability.

[BibT_eX]

[DOI]

Proceedings of the Reachability Problems, 3rd International Workshop, 2009

High Complexity Tilings with Sparse Errors.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Complex tilings.

[BibT_eX]

[DOI]

Leonid A. Levin

J. Symb. Log., 2008

A Simple Proof of Miller-Yu Theorem.

[BibT_eX]

[DOI]

Wolfgang Merkle

Fundam. Informaticae, 2008

Fixed Point and Aperiodic Tilings.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Algorithmic randomness and splitting of supermartingales

[BibT_eX]

[DOI]

Alexey V. Chernov

CoRR, 2008

Limit complexities revisited.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

Sparse sets.

[BibT_eX]

Proceedings of the First Symposium on Cellular Automata "Journées Automates Cellulaires" (JAC 2008), 2008

Prequential Randomness.

[BibT_eX]

[DOI]

Vladimir Vovk

Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

On-Line Probability, Complexity and Randomness.

[BibT_eX]

[DOI]

Alexey V. Chernov

Vladimir Vovk

Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

2007

Non-reducible descriptions for conditional Kolmogorov complexity.

[BibT_eX]

[DOI]

Mikhail Ustinov

Michael V. Vyugin

Theor. Comput. Sci., 2007

2006

Multisource algorithmic information theory

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Combinatorial proof of Muchnik's theorem.

[BibT_eX]

[DOI]

Proceedings of the Kolmogorov Complexity and Applications, 29.01. - 03.02.2006, 2006

2005

Partitioning multi-dimensional sets in a small number of "uniform" parts

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

2004

Non-reducible descriptions for conditional Kolmogorov complexity

[BibT_eX]

[DOI]

Andrei A. Muchnik

Michael V. Vyugin

Electron. Colloquium Comput. Complex., 2004

2002

Logical operations and Kolmogorov complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Combinatorial interpretation of Kolmogorov complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Descriptive complexity of computable sequences.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Upper semi-lattice of binary strings with the relation "x is simple conditional to y".

[BibT_eX]

[DOI]

Alexey V. Chernov

Andrei A. Muchnik

Theor. Comput. Sci., 2002

Basic set theory.

[BibT_eX]

Student mathematical library 17, American Mathematical Society, ISBN: 978-0-8218-2731-4, 2002

2000

Inequalities for Shannon Entropy and Kolmogorov Complexity.

[BibT_eX]

[DOI]

Daniel Hammer

J. Comput. Syst. Sci., 2000

1999

Discussion on Kolmogorov Complexity and Statistical Analysis.

[BibT_eX]

[DOI]

Comput. J., 1999

Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y".

[BibT_eX]

[DOI]

Andrei A. Muchnik

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

A Strange Application of Kolmogorov Complexity.

[BibT_eX]

[DOI]

Daniel Hammer

Theory Comput. Syst., 1998

1997

Inequalities for Shannon entropies and Kolmogorov complexities.

[BibT_eX]

[DOI]

Daniel Hammer

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Algorithms and programming - problems and solutions.

[BibT_eX]

Birkhäuser, ISBN: 978-0-8176-3847-4, 1997

1996

Relations Between Varieties of Kolmogorov Complexities.

[BibT_eX]

[DOI]

Vladimir A. Uspensky

Math. Syst. Theory, 1996

1994

Low-degree Tests.

[BibT_eX]

[DOI]

Katalin Friedl

Zsolt Hátsági

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Algebra.

[BibT_eX]

[DOI]

Israel M. Gelfand

Birkhäuser, ISBN: 978-0-8176-3677-7, 1993

1992

IP = PSPACE: Simplified Proof.

[BibT_eX]

[DOI]