Paul M. B. Vitányi

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

Towards an Algorithmic Statistics.

[BibT_eX]

[DOI]

Péter Gács

John Tromp

Proceedings of the Algorithmic Learning Theory, 11th International Conference, 2000

1999

Kolmogorov Random Graphs and the Incompressibility Method.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method.

[BibT_eX]

[DOI]

Harry Buhrman

Jaap-Henk Hoepman

SIAM J. Comput., 1999

Mutual Search.

[BibT_eX]

[DOI]

J. ACM, 1999

Average-Case Complexity of Shellsort (Preliminary version)

[BibT_eX]

[DOI]

CoRR, 1999

New Applications of the Incompressibility Method.

[BibT_eX]

[DOI]

Comput. J., 1999

Average-Case Complexity of Shellsort.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

New Applications of the Incompressibility Method.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

The Expected Size of Heilbronn's Triangles.

[BibT_eX]

[DOI]

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

Some Examples of Average-case Analysis by the Imcompressibility Method.

[BibT_eX]

Proceedings of the Jewels are Forever, 1999

1998

Information Distance.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1998

Randomized Naming Using Wait-Free Shared Variables.

[BibT_eX]

[DOI]

Alessandro Panconesi

Marina Papatriantafilou

Philippas Tsigas

Distributed Comput., 1998

New Applications of the Incompressibility Method: Part I

[BibT_eX]

[DOI]

CoRR, 1998

Mutual Search (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Average-Case Analysis Using Kolgomorov Complexity (Abstract).

[BibT_eX]

Proceedings of Computing: The Fourth Australasian Theory Symposium (CATS'98), 1998

1997

Erratum: "Two heads are better that two tapes".

[BibT_eX]

[DOI]

Joel I. Seiferas

J. ACM, 1997

Two heads are better than two tapes.

[BibT_eX]

[DOI]

Joel I. Seiferas

J. ACM, 1997

Reversibility and Adiabatic Computation: Trading Time and Space for Energy

[BibT_eX]

[DOI]

CoRR, 1997

Reversible Simulation of Irreversible Computation by Pebble Games

[BibT_eX]

[DOI]

John Tromp

CoRR, 1997

Kolmogorov random graphs.

[BibT_eX]

[DOI]

Harry Buhrman

Proceedings of the Compression and Complexity of SEQUENCES 1997, 1997

Average-Case Analysis via Incompressibility.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

On Prediction by Data Compression.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning: ECML-97, 1997

Mutual Search (abstract).

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997

Average-Case Analysis Using Kolmogorov Complexity.

[BibT_eX]

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

An introduction to Kolmogorov complexity and its applications, Second Edition.

[BibT_eX]

[DOI]

Graduate Texts in Computer Science, Springer, ISBN: 978-1-4757-2606-0, 1997

1996

How to Share Concurrent Wait-Free Variables.

[BibT_eX]

[DOI]

John Tromp

J. ACM, 1996

Optimal Routing Tables.

[BibT_eX]

[DOI]

Harry Buhrman

Jaap-Henk Hoepman

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

Reversible Simulation of Irreversible Computation.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

Genetic Fitness Optimization Using Rapidly Mixing Markov Chains.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996

1995

A New Approach to Formal Language Theory by Kolmogorov Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

Algorithmic Arguments in Physics of Computation.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Physics and the New Computation.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

Computational Machine Learning in Theory and Praxis.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Today: Recent Trends and Developments, 1995

1994

Statistical Properties of Finite Sequences with High Kolmogorov Complexity.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1994

Kolmogorov Complexity Arguments in Combinatorics.

[BibT_eX]

J. Comb. Theory, Ser. A, 1994

Randomized Wait-Free Naming.

[BibT_eX]

[DOI]

Alessandro Panconesi

Marina Papatriantafilou

Philippas Tsigas

Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

Model selection for neural networks: comparing MDL and NIC.

[BibT_eX]

[DOI]

Guido M. te Brake

Joost N. Kok

Proceedings of the 2nd European Symposium on Artificial Neural Networks, 1994

1993

Thermodynamics of computation and information distance.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

An introduction to Kolmogorov complexity and its applications.

[BibT_eX]

[DOI]

Texts and Monographs in Computer Science, Springer, ISBN: 978-1-4757-3860-5, 1993

1992

The Power of the Queue.

[BibT_eX]

[DOI]

Luc Longpré

SIAM J. Comput., 1992

A Note on Weighted Distributed Match-Making.

[BibT_eX]

[DOI]

Evangelos Kranakis

Math. Syst. Theory, 1992

Inductive Reasoning and Kolmogorov Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

Optimality of Wait-Free Atomic Multiwriter Variables.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

Average Case Complexity Under the Universal Distribution Equals Worst-Case Complexity.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

Wait-free Test-and-Set (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Philosophical Issues in Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Inductive reasoning.

[BibT_eX]

[DOI]

Proceedings of the Language Computations, 1992

1991

Learning Simple Concept Under Simple Distributions.

[BibT_eX]

[DOI]

SIAM J. Comput., 1991

Combinatorics and Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

An introduction to Kolmogorov - complexity and its applications ; part 1: theory.

[BibT_eX]

CWI, 1991

1990

Kolmogorov Complexity and its Applications.

[BibT_eX]

Proceedings of the Handbook of Theoretical Computer Science, 1990

1989

A New Approach to Formal Language Theory by Kolmogorov Complexity (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

How to Share Concurrent Asynchronous Wait-Free Varaibles (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Inductive Reasoning and Komogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

Tape versus Queue and Stacks: The Lower Bounds

[BibT_eX]

[DOI]

Inf. Comput., July, 1988

Locality, Communication, and Interconnect Length in Multicomputers.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

Counting is easy.

[BibT_eX]

[DOI]

Joel I. Seiferas

J. ACM, 1988

Distributed Match-Making.

[BibT_eX]

[DOI]

Sape J. Mullender

Algorithmica, 1988

A Proof Technique for Register Automicity.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1988

Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich Kolmogorov 1903-87.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

Weighted Distributed Match-Making.

[BibT_eX]

[DOI]

Evangelos Kranakis

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987

Atomic Multireader Register.

[BibT_eX]

[DOI]

Lefteris M. Kirousis

Evangelos Kranakis

Proceedings of the Distributed Algorithms, 1987

Errata to "Atomic Shared Register Access by Asynchronous Hardware"

[BibT_eX]

[DOI]

Baruch Awerbuch

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986

Distributed Match-Making for Processes in Computer Networks (Preliminary Version).

[BibT_eX]

[DOI]

Sape J. Mullender

ACM SIGOPS Oper. Syst. Rev., 1986

Atomic Shared Register Access by Asynchronous Hardware (Detailed Abstract)

[BibT_eX]

[DOI]

Baruch Awerbuch

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

Nonsequentail Computation and Laws of Nature.

[BibT_eX]

[DOI]

Proceedings of the VLSI Algorithms and Architectures, 1986

1985

An Optimal Simulation of Counter Machines: The ACM Case.

[BibT_eX]

[DOI]

SIAM J. Comput., 1985

An Optimal Simulation of Counter Machines.

[BibT_eX]

[DOI]

SIAM J. Comput., 1985

An n<sup>1.618</sup> Lower Bound on the Time to Simulate One Queue or Two Pushdown Stores by One Tape.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1985

Square Time is Optimal for Simulation of One Pushdown Store or One Queue by an Oblivious One-Head Tape Unit.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1985

Logarithmic signal propagation delay and the efficiency of VLSI circuits.

[BibT_eX]

Bull. EATCS, 1985

Area Penalty for Sublinear Signal Propagation Delay on Chip (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

On the Simulation of Many Storage Heads by One.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1984

On Two-Tape Real-Time Computation and Queues.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1984

On the Power of Real-Time Two-Way Multihead Finite Automata With Jumps.

[BibT_eX]

[DOI]

Walter J. Savitch

Inf. Process. Lett., 1984

Big omega versus the wild functions.

[BibT_eX]

Lambert G. L. T. Meertens

Bull. EATCS, 1984

Distributed Elections in an Archimedean Ring of Processors (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

The Simple Roots of Real-Time Computation Hierarchies (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1984

1983

On the Simulation of Many Storage Heads by a Single One (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1983

1982

On Efficient Simulations of Multicounter Machines

[BibT_eX]

[DOI]

Inf. Control., 1982

Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines

[BibT_eX]

[DOI]

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981

How well can a graph be n-colored?

[BibT_eX]

[DOI]

Discret. Math., 1981

1980

Achievable High Scores of epsilon-Moves and Running Times in DPDA Computations.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1980

Relativized Obliviousness.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1980 (MFCS'80), 1980

On the Power of Real-Time Machines Under Varying Specifications (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1980

1978

Stable String Languages of Lindenmayer Systems

[BibT_eX]

[DOI]

Adrian Walker

Inf. Control., May, 1978

On Inverse Deterministic Pushdown Transductions.

[BibT_eX]

[DOI]

Walter J. Savitch

J. Comput. Syst. Sci., 1978

A note on the recursive enumerability of some classes of recursively enumerable languages.

[BibT_eX]

[DOI]

Peter van Emde Boas

Inf. Sci., 1978

1977

Context Sensitive Table Lindenmayer Languages and a Relation to the LBA Problem

[BibT_eX]

[DOI]

Inf. Control., March, 1977

Linear Time Simulation of Multihead Turing Machines with Head-to-Head Jumps.

[BibT_eX]

[DOI]

Walter J. Savitch

Proceedings of the Automata, 1977

1976

Deterministic Lindenmayer Languages, Nonterminals and Homomorphisms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1976

On a problem in the collective behavior of automata.

[BibT_eX]

[DOI]

Discret. Math., 1976

1975

Digraphs Associated with DOL Systems.

[BibT_eX]

Proceedings of the Automata, Languages, Development: At the crossroads of biology, mathematics and computer science, result of an international conference held at Noordwijkerhout, The Netherlands, March 31, 1975

1974

Growth of Strings in Context Dependent Lindenmayer Systems.

[BibT_eX]

[DOI]

Proceedings of the L Systems, 1974

On the Size of D0L Languages.

[BibT_eX]

[DOI]