Contents

Part I What Is a Computational Structure?

Ordinary data structures, treated from first principles: elements, relations, operations, representations and costs — before any new notation.

1. 1Structures, Representations, and Operations

   Elements, relations, state, operations and machine models — and the three questions this book never lets collapse into one.

   mixed
2. 2Arrays: Addresses You Can Compute

   The array as the first and purest example of a grammar whose words are arithmetic — and what that costs when the array must grow, shift or become multidimensional.

   mixed
3. 3Lists, Stacks, Queues, and Deques

   Pointer-based sequences, and the first structure whose language of defined operation sequences is not regular.

   mixed
4. 4Hash Tables, Sets, Maps, and Tries

   When names are not dense numbers — hashing computes an address anyway, at the price of collisions; tries turn keys into words read by an automaton.

   mixed
5. 5Trees, Heaps, Search Trees, and Forests

   Tree addresses as words, the heap numeration and exactly when it gives constant-time navigation, search trees, and forests compressed by sharing.

   mixed
6. 6Graphs and Paths

   Graph representations, walks versus simple paths, and the relational semantics that makes "a path is an edge followed by a path" a theorem rather than a slogan.

   mixed

Part II Grammar as a Computational Object

The formal core: operational grammars, three semantic layers, and the admissibility languages that constrain operations.

1. 7Operational Grammars

   The formal object of Computational Grammar Theory — moves, relational semantics, admissibility languages, adequate representations, cost profiles — and the five mechanisms through which grammar can affect cost.

   mixed
2. 8Admissibility Languages and the Product Construction

   How an admissibility language is compiled into an automaton, how a structure is searched under it, and exactly how much a constraint can help or hurt.

   mixed

Part III Classical Algorithms Reconstructed

Baseline algorithms with proofs, implementations and counted costs, each mapped to its grammar — including the many cases where grammar adds nothing.

1. 9Searching and Sorting Reconstructed

   Linear and binary search, four comparison sorts and counting sort — with invariants, counted costs, the comparison lower bound, and the one way around it.

   mixed
2. 10Graph Algorithms Reconstructed

   Traversal, ordering, components, shortest paths, spanning trees and closure — and the theorem that evaluating a path grammar is computing a closure, with cost depending on the grammar's shape.

   mixed
3. 11Range Queries, Dynamic Programming, and Strings

   Fenwick and segment trees as arithmetic addressing, sparse tables as precomputation, dynamic programming as shared derivations, and string matching as automata.

   mixed

Part IV Cost, Information, and the Limits of Grammar

Preprocessing, information lower bounds, compiled operations, and what grammars cannot do to complexity classes.

1. 12Cost Profiles, Preprocessing, and Information

   When does precomputing pay? What is the least information a "grammar of all answers" must contain? And what happens when the structure changes?

   mixed
2. 13Compiling Operations: When Grammar Becomes Arithmetic

   A move word of any length can be compiled into a constant-size operation on some structures and provably not on others. This chapter finds the line.

   Proved here
3. 14The Limits: Advice, Restriction, and P versus NP

   What a grammar can and cannot do to complexity classes — stated as precise challenges with their proof obligations, and answered.

   mixed

Part V PageRank, Search, and Information Retrieval

A long-form case study: the mathematics of PageRank from first principles, and what a grammatical view does and does not add.

1. 15PageRank from First Principles

   The random surfer, stochastic matrices, dangling pages, damping, existence and uniqueness of the ranking, power iteration with certified error, solvers, sparse representations, updates and personalization.

   mixed
2. 16PageRank Through the Lens of Grammar

   The random surfer as a probabilistic operational grammar, rankings constrained by admissibility languages, block structure as a structural grammar — and an honest list of what the grammatical view does not improve.

   mixed

Part VI Modern Computational Systems

Explicit models of computation graphs, retrieval, vector search and agent workflows — and careful limits on what grammar can claim about them.

1. 17Computation Graphs, Retrieval, and Agent Systems

   Where computational grammars apply to modern AI systems — computation graphs, attention masks, retrieval pipelines, vector search and agent workflows — and where they do not.

   mixed

Part VII The Laboratory, the SDK, and Grammar as a Service

The executable companion: how to use, extend and serve computational grammars.

1. 18The CGT SDK

   A tutorial for the executable companion to this book — structures, grammars, the three layers, cost models, comparisons, experiment records and extension points.

   mixed
2. 19Grammar as a Service

   A contract for requesting operations on versioned grammars, with layered rejection, quotas, determinism, provenance and cache validity — and an argument about what should run where.

   Proposed

Part VIII Conclusions

What has actually been established, what has not, and where the research goes next.

1. 20What Computational Grammar Theory Has Established

   The confirmed contributions, the negative results, the open questions and the research agenda — without inflating any of them.

   mixed

Appendices

1. Appendix ANotation and Conventions

   The symbols, cost conventions and evidence labels used throughout the book.

   Definition
2. Appendix BReproducing This Book

   How to rerun every experiment, test, example and build step, and what reproducibility means for each.

   Definition