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
3 Edge complexity and digraphs
3.1 Edge-counting automatic complexity