Automatic Complexity

Preface ▶
- How to use this book.
- Acknowledgments.
1 First steps in automatic complexity ▶
- 1.1 Words ▶
  - 1.1.1 Occurrences and powers
2 Nondeterminism and overlap-free words
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

4 The many variants