• Preface ▶
    • How to use this book.
    • Acknowledgments.
  • 1 First steps in automatic complexity ▶
    • 1.1 Words ▶
      • 1.1.1 Occurrences and powers
    • 1.2 Automata
  • 2 Nondeterminism and overlap-free words ▶
    • 2.1 Introduction
  • 3 Edge complexity and digraphs ▶
    • 3.1 Edge-counting automatic complexity
  • 4 The many variants ▶
    • 4.1 Master diagram
  • 5 The incompressibility theorem
  • 6 Conditional automatic complexity ▶
    • 6.1 Basics
  • 7 Logical depth and automatic complexity ▶
    • 7.1 Introduction
  • 8 Bibliography
  • Dependency graph

Automatic Complexity

Bjørn Kjos-Hanssen

This Lean project contains solutions to the exercises in the book Automatic complexity: a computable measure of irregularity published by de Gruyter, and excerpts from the book itself.

  • Preface
    • How to use this book.
    • Acknowledgments.
  • 1 First steps in automatic complexity
    • 1.1 Words
      • 1.1.1 Occurrences and powers
    • 1.2 Automata
  • 2 Nondeterminism and overlap-free words
    • 2.1 Introduction
  • 3 Edge complexity and digraphs
    • 3.1 Edge-counting automatic complexity
  • 4 The many variants
    • 4.1 Master diagram
  • 5 The incompressibility theorem
  • 6 Conditional automatic complexity
    • 6.1 Basics
  • 7 Logical depth and automatic complexity
    • 7.1 Introduction
  • 8 Bibliography