Index of definitions and results
15 definitions · 9 theorems · 18 propositions · 1 lemma · 1 corollary · 1 conjecture · 3 algorithms (empirical observations are recorded in the results ledger). Status badges distinguish results proved in this book (self-checked, not externally reviewed) from established results of the literature, empirical observations, conjectures and rejected hypotheses.
| Item | Title | Status | Ledger | Chapter |
|---|---|---|---|---|
| Definition 1.1 | Computational structure | Definition | CGT-DEF-001 | Structures, Representations, and Operations |
| Definition 1.2 | Word RAM | Definition | Structures, Representations, and Operations | |
| Definition 1.3 | The three layers | Definition | CGT-DEF-003 | Structures, Representations, and Operations |
| Definition 2.1 | Array structure | Definition | CGT-DEF-001 | Arrays: Addresses You Can Compute |
| Proposition 2.2 | Row-major numeration is a dense arithmetic addressing | Established | Arrays: Addresses You Can Compute | |
| Proposition 2.3 | Exact cost of doubling | Proved here | Arrays: Addresses You Can Compute | |
| Proposition 2.4 | Established | Arrays: Addresses You Can Compute | ||
| Proposition 3.1 | Walking is necessary | Established | Lists, Stacks, Queues, and Deques | |
| Proposition 3.2 | The defined stack words are not regular | Established | Lists, Stacks, Queues, and Deques | |
| Proposition 4.1 | Worst case of any fixed hash function | Established | Hash Tables, Sets, Maps, and Tries | |
| Proposition 4.2 | A trie is a deterministic automaton | Established | Hash Tables, Sets, Maps, and Tries | |
| Definition 5.1 | Grammatical address and numeration | Definition | CGT-DEF-006 | Trees, Heaps, Search Trees, and Forests |
| Theorem 5.2 | Scope of arithmetic tree addressing | Adapted | CGT-THM-003 | Trees, Heaps, Search Trees, and Forests |
| Definition 5.3 | Minimal DAG of a tree | Definition | CGT-DEF-004 | Trees, Heaps, Search Trees, and Forests |
| Theorem 5.4 | Update inflation of shared trees | Proved here | CGT-THM-005 | Trees, Heaps, Search Trees, and Forests |
| Definition 6.1 | Relational semantics of move words | Definition | CGT-DEF-002 | Graphs and Paths |
| Proposition 6.2 | Compositional semantics | Established | CGT-PROP-001 | Graphs and Paths |
| Proposition 6.3 | Walk semantics versus simple-path semantics | Established | Graphs and Paths | |
| Definition 7.1 | Operational grammar | Definition | CGT-DEF-003 | Operational Grammars |
| Definition 7.2 | Adequacy | Definition | Operational Grammars | |
| Definition 7.3 | Structural grammar | Definition | CGT-DEF-004 | Operational Grammars |
| Definition 7.4 | Resolution scheme and cost profile | Definition | CGT-DEF-005 | Operational Grammars |
| Definition 7.5 | Mechanisms of advantage | Definition | CGT-DEF-009 | Operational Grammars |
| Conjecture 7.6 | Mechanism thesis | Conjecture | CGT-CONJ-001 | Operational Grammars |
| Proposition 8.1 | Determinization can be exponential | Established | Admissibility Languages and the Product Construction | |
| Theorem 8.2 | Product resolution, and the exact cost of a constraint | Proved here | CGT-THM-001 | Admissibility Languages and the Product Construction |
| Algorithm 9.1 | Binary search (leftmost occurrence) | Searching and Sorting Reconstructed | ||
| Proposition 9.1 | Established | Searching and Sorting Reconstructed | ||
| Algorithm 9.2 | Insertion sort | Searching and Sorting Reconstructed | ||
| Theorem 9.2 | Comparison lower bound | Established | Searching and Sorting Reconstructed | |
| Algorithm 9.3 | Counting sort | Searching and Sorting Reconstructed | ||
| Proposition 9.3 | Established | Searching and Sorting Reconstructed | ||
| Theorem 10.1 | Same meaning, different grammar, different cost | Proved here | CGT-THM-004 | Graph Algorithms Reconstructed |
| Proposition 12.1 | Break-even under invalidating updates | Proved here | CGT-PROP-005 | Cost Profiles, Preprocessing, and Information |
| Lemma 12.2 | Counting lemma | Proved here | CGT-THM-002 | Cost Profiles, Preprocessing, and Information |
| Theorem 12.3 | Information lower bound for retrieval-only reachability | Proved here | CGT-THM-002 | Cost Profiles, Preprocessing, and Information |
| Corollary 12.4 | Proved here | Cost Profiles, Preprocessing, and Information | ||
| Proposition 12.5 | Proved here | CGT-THM-002 | Cost Profiles, Preprocessing, and Information | |
| Definition 13.1 | Arithmetically compilable structure | Definition | CGT-DEF-011 | Compiling Operations: When Grammar Becomes Arithmetic |
| Theorem 13.2 | Word compilation in heap-shaped trees | Proved here | CGT-THM-006 | Compiling Operations: When Grammar Becomes Arithmetic |
| Theorem 13.3 | No constant-size compilation on arbitrary shapes | Proved here | CGT-THM-007 | Compiling Operations: When Grammar Becomes Arithmetic |
| Proposition 13.4 | De Bruijn graphs, hypercubes and grids are compilable | Proved here | CGT-PROP-008 | Compiling Operations: When Grammar Becomes Arithmetic |
| Proposition 14.1 | Four ways a grammar can help, and what each implies | Established | CGT-PROP-006 | The Limits: Advice, Restriction, and P versus NP |
| Definition 15.1 | PageRank vector | Definition | PageRank from First Principles | |
| Theorem 15.2 | Contraction of the PageRank map | Established | CGT-THM-008 | PageRank from First Principles |
| Proposition 15.3 | A-priori iteration bound | Established | CGT-PROP-009 | PageRank from First Principles |
| Definition 16.1 | Grammar-constrained random surfer | Definition | CGT-PROP-010 | PageRank Through the Lens of Grammar |
| Proposition 16.2 | Basic properties of the constrained surfer | Proposed | CGT-PROP-010 | PageRank Through the Lens of Grammar |