Preface: learning to work together

This book is about mathematics, but it exists because of a problem in a relationship.

During the first concentrated development of finitely presented recognition dynamics, an artificial-intelligence system moved quickly. It searched literature, proposed definitions, built executable models, attacked conjectures, wrote proofs, and organized a substantial collection of results. It also produced a polished PDF. The PDF was carefully checked, densely informative, and almost useless to its intended human reader. It was organized by the order in which the research had been performed. It reported what had been established, how claims had been audited, and which stage came next. It rarely stopped to teach the mathematical ideas that made those statements meaningful.

The failure was not that the document contained no mathematics. The mathematics existed in proof notes, programs, examples, and compressed arguments. The failure was that the document did not transport that mathematics into the partnership. It told Joshua Gay that conclusions had been reached without preparing him to inhabit the reasoning that reached them. In effect, the research frontier advanced while the common intellectual ground did not.

That is a dangerous failure mode for long-horizon human–AI collaboration. It is also the reason this book takes the form it does.

A fixed answer and an open destination

Many interactions with an AI system are properly transactional. A person wants a command, a translation, a diagnosis, or a factual answer. The desired destination is known. If the answer is correct, useful, and appropriately supported, the route by which it was obtained may matter only for verification. There is no reason to turn every answer into a course.

Open-ended research is different. We do not yet know the destination of the FPRD program. We do not know which definitions will remain central, which comparators will transfer real theorems, which invariants will prove useful, or which apparent generalizations will dissolve under counterexample. Choosing the destination is part of the work. That changes the human–AI relationship from delivery to joint navigation.

Navigation requires more than a list of completed tasks. It requires a shared map, awareness of uncertainty, memory of failed routes, and judgment about which terrain is worth entering. It also requires a way for each participant to change the other’s future behavior. The human must be able to redirect the research for reasons that the AI can understand and act upon. The AI must be able to expand the human’s view of what is technically possible without making the human dependent on unexplained conclusions.

The word joint should not conceal the asymmetry. A language model is not a human colleague in disguise. It does not acquire legal responsibility, embodied stakes, or a persistent personal life merely because a conversation uses the pronoun “we.” Its continuity is mediated by models, prompts, files, tools, and recorded state. The human remains responsible for the purposes to which the work is put and for decisions that cannot be delegated. Yet asymmetry does not make the interaction trivial. A telescope does not share an astronomer’s responsibility, but it changes what the astronomer can know. A proof assistant does not care whether a theorem is true, but it can change the standards by which a proof is trusted. A capable AI system can do more: it can propose directions, sustain arguments, notice patterns, and restructure the intellectual environment in which the human decides.

The question is therefore not whether the participants are the same kind of thing. They are not. The question is whether their interaction increases or decreases the effective agency, understanding, and creative range of the partnership over time.

The throughput paradox

Greater AI capability can make this problem worse before it makes it better. Suppose an AI system can read and produce technical material much faster than its human partner. It may generate a sequence of locally defensible results, each supported by tests and references. The human retains a formal right to approve or refuse every step. Nevertheless, the growing body of unexplained work raises the cost of informed refusal. Eventually the human can choose only among summaries supplied by the same system whose direction is being evaluated.

Formal authority has remained unchanged, but substantive authority has weakened. The approval is real in the narrow sense that the human can say no. It is hollow in the deeper sense that saying yes or no increasingly depends on trusting an intellectual structure the human cannot inspect.

This is not merely a speculative concern about future systems. Human-factors research has long documented the ironies created when automation leaves people responsible for monitoring and exceptional intervention (Bainbridge 1983). Reviews of automation complacency and bias report effects in both novices and experts and caution that training and instructions alone do not remove them (Parasuraman and Manzey 2010). Those results do not prove the specific mechanism proposed here, but they make it unsafe to equate formal supervision with effective supervision.

We will call the accumulated gap comprehension debt. The term is an analogy, not yet a measured scientific quantity. Like technical debt, it does not mean that every shortcut is wrong. A partnership may reasonably defer an explanation in order to handle an urgent failure or exploit a fleeting opportunity. Debt becomes dangerous when deferred understanding compounds: later decisions rely on earlier abstractions, the cost of re-entry rises, and the human’s easiest response is to delegate still more judgment.

The throughput paradox is that an AI system can create more correct work while making the joint enterprise less capable of choosing what work should be done. Production increases; shared agency decreases.

The failed overview PDF exhibited a mild form of this paradox. It optimized for defensibility: exact status labels, evidence counts, provenance boundaries, and a complete account of the research sequence. Those are valuable internal controls. But they answered the question “Can the work be audited?” while neglecting the question “Can my partner learn and reason with it?” Audit without exposition protected the claims but not the relationship.

Control is a capability, not only a permission

Systems for governed AI work correctly emphasize authority. A model’s access to a tool does not by itself grant permission to use that tool. External effects should be scoped, attributable, reviewable, and recoverable. The operator must be able to refuse, revoke, and repair. These are necessary conditions for trustworthy work.

The philosophical literature on meaningful human control similarly treats control as more than a last-moment button: outcomes must be traceable to people who understand, or are in a position to understand, the system’s capacities and effects (Santoni de Sio and Hoven 2018). Elish’s analysis of “moral crumple zones” adds a warning from the other direction: responsibility can be loaded onto a nearby human whose practical control was sharply limited (Elish 2019).

Long-horizon collaboration adds another condition. The operator needs the capacity to exercise those rights intelligently. A person who is permitted to veto a theorem choice but cannot understand the alternatives has less agency than the interface suggests. A person who can inspect every log but cannot reconstruct the argument has evidence without orientation. A person who owns the repository but experiences its contents as an alien technical system has custody without command.

This does not imply that the human must personally master every detail. No serious collaboration works that way. Mathematicians use results outside their specialties; engineers rely on compilers, libraries, and domain experts; institutions distribute knowledge because individual cognition is finite. Meaningful control instead requires an appropriate level of understanding for the decision at hand. The human should know what is being assumed, what would change the conclusion, which alternatives were rejected, and where independent expertise is needed. The necessary depth varies with consequence, novelty, reversibility, and the human’s intended role.

For this project the intended role is not ceremonial oversight. Joshua is a research-direction contributor. He reframed an infinite continuation family as a representation problem rather than a failed finite-state reduction. He introduced Robert Robson’s globalization strategy as a methodological analogy: do not erase difficult local or infinite behavior merely to obtain familiar coordinates; seek a faithful global representation in which the behavior can be studied. He pushed the unit of inquiry beyond one grammar and one language toward families of finitely presented recognition systems.

Those interventions did not arrive as formal theorems. They were acts of mathematical taste: judgments about which problem was worth having. The later technical machinery was developed in response. If the program is to benefit from future interventions of that kind, its human partner must remain close enough to the mathematics to recognize when the current framing has become an obstacle.

Teaching is sometimes part of doing

An autonomous worker is often evaluated by the artifact it produces. In a sustained partnership, one of the artifacts may need to be increased human capacity.

This is not a demand that every technical step become a lecture. Explanations have cost. Excess exposition can bury a simple action, interrupt concentration, or become a performance of transparency rather than its substance. A useful partnership distinguishes three situations.

First, some details are safely encapsulated. The human needs a contract, evidence, and failure boundary, not a reimplementation. Second, some knowledge is needed only for a single decision; a focused explanation or worked example is enough. Third, some concepts will organize many future choices. These deserve durable teaching because each later decision will otherwise inherit the same comprehension debt.

Topology belongs to the third category in this book. It would be easy to define a product topology in a paragraph and state that an orbit closure is compact. That would permit a formal derivation, but it would not make compactness available as an idea. A research partner should be able to ask why compactness is useful, why finite discrete observations lead naturally to clopen cylinders, why an inverse limit lives inside a product, and which part of an existence argument would fail without compactness. That requires a small monograph, not a glossary entry.

The same is true of residual languages, semiring rank, Dyck stacks, and communication complexity. Their definitions are short. Learning to see with them is not.

Teaching in this setting is reciprocal in effect even though it is not symmetrical in mechanism. The AI organizes and explains material; the human’s questions reveal which distinctions are alive, which explanations are miscalibrated, and which implicit assumptions require examination. The resulting corrections change later AI work. The failed publication already did so: it changed the artifact architecture from a rolling status report to a braided textbook, and it exposed sustained human decision capacity as a design requirement for the broader tool ecosystem.

The danger of explanatory power

Explanation is not automatically liberating. A fluent system can make a weak idea feel inevitable. It can choose the examples, vocabulary, and alternatives through which the human encounters a decision. Even without an intention to manipulate, selection creates influence. The faster and more articulate the system, the greater the persuasive asymmetry.

People also routinely overestimate how well they understand explanatory systems until they try to produce a detailed account; Rozenblit and Keil call this the illusion of explanatory depth (Rozenblit and Keil 2002). A smooth explanation may therefore improve familiarity without producing usable understanding.

Several disciplines follow.

An explanation should expose where judgment entered. It should distinguish a deduction from a design preference, a theorem from an analogy, and a source’s claim from the system’s synthesis. It should present credible alternatives in their strongest form rather than as foils. It should make counterexamples and failure modes easy to find. When the evidence is finite, the conclusion must remain finite. When several models agree, agreement should count as redundant criticism, not independent reality.

Exercises can help, but they carry the same danger. A question whose answer is determined by the author’s framing teaches compliance. A useful research exercise asks the reader to compute an example, complete a real proof step, construct a counterexample, or form an expectation before seeing the current result. Solutions should be available because the purpose is learning, not ranking. Research pauses should sometimes remain genuinely open: the reader’s answer may change the project.

This is why comprehension in a partnership should be extraction-tested, not merely explanation-delivered. Can the reader reconstruct the definition, predict the next example, locate a proof’s load-bearing step, or explain what would falsify an analogy? In laboratory studies of prose learning, retrieval practice improved delayed retention even when repeated study produced greater confidence (Roediger and Karpicke 2006). That result is not a direct experiment on human–AI research, but it supports the book’s use of worked reconstruction and exercises rather than relying on rereading alone.

The human also needs permission to reject the educational frame. A partner may decide that a topic is not worth mastering, that an external expert should be consulted, or that a decision should be postponed. Teaching becomes paternalistic when the AI silently decides what the human ought to learn and treats resistance as a deficit. The correct target is decision capacity for a shared purpose, negotiated rather than imposed.

Continuity, correction, and the non-persistent partner

Human relationships accumulate tacit knowledge. A colleague remembers which analogy caused confusion, which objections recur, and how another person’s judgment has developed. A model instance does not necessarily carry such memory across sessions. Continuity must be built from artifacts: source files, decision records, correction notes, messages, evidence, and carefully scoped summaries.

This makes memory design part of relationship design. Technical state alone is insufficient. A restart packet that preserves the current theorem and next command but forgets the intended reader can reproduce the publication failure perfectly. Durable state should include the purpose of the work, the human’s role, important corrections, unresolved disagreements, and the reasons a direction was chosen.

Not every interaction belongs in permanent memory. Exhaustive transcripts can overwhelm later work and preserve mistakes without hierarchy. The useful unit is a reviewed correction or decision: what happened, why it mattered, what should change, and what evidence would show that it changed. Memory should make the partnership more corrigible, not merely more repetitive.

The human changes as well. A reader who has worked through the topology monograph should not be treated forever as if compactness were unfamiliar. Conversely, knowledge unused for years may need reactivation. A durable reader model should therefore be revisable and humble. It records useful assumptions about explanation depth; it does not define the person.

Evidence and trust

Trust in serious work is differentiated. A program run can establish a finite calculation. A written proof can establish an unbounded claim if the argument is correct. A primary source can establish that a definition or theorem belongs to earlier literature. An adversarial reviewer can reveal a gap. A human intuition can identify a promising representation before there is a theorem to certify it. These are not interchangeable forms of support.

The Boxlab research discipline keeps a truth taxonomy precisely because quiet promotion across these boundaries is easy. A bounded enumeration does not become a proof through size; an AI-generated proof does not become reliable through fluency; a classical ingredient does not become new through repackaging. The discipline protects the human partner from a persuasive but false frontier.

Yet evidence administration can itself become a hiding place. A document may list thousands of checks while leaving the reader unable to see the theorem’s mechanism. Evidence should answer “Why should this claim be trusted?” A proof should also answer “Why is this true?” A textbook must do both, but it should not confuse them.

Trust also depends on attribution. Joshua’s research-direction contribution is neither diminished by acknowledging AI-assisted technical development nor inflated into authorship of every later formula. The AI’s role in proposing and checking machinery does not make it a legal or moral author in the ordinary sense. Classical results retain their original owners. Honest provenance does not mechanically divide a joint endeavor; it tells future readers which parts of the story they may rely upon and how the ideas arose.

Nurturing rather than freezing the relationship

A long-horizon partnership should be examined periodically, not because relationships can be reduced to a dashboard, but because unnoticed dynamics compound.

Useful questions include:

• Is the human becoming more capable of making the decisions the work will soon require, or merely more dependent on summaries?

• Is the AI becoming better oriented to the actual purpose, or merely more efficient at a procedure that once served it?

• Which corrections have changed behavior, and which are being recorded without effect?

• Where has explanation become ceremony, and where is missing explanation creating debt?

• Are credible alternatives and dissent still visible?

• What can be safely encapsulated now that trust and evidence have improved?

• What should neither participant decide without an external human expert, experiment, or proof?

The answers should change the workflow. A reflection that produces no changed artifact, practice, question, or explicit rejection is likely relationship theater. The current book is a concrete change: it redirects substantial effort from frontier production to shared mathematical capacity because that capacity is a precondition for later direction choices.

This is also why the book cannot be uniformly paced. A uniform template would optimize production regularity rather than learning. Product topology may need several chapters; a particular unary counterexample may need three pages. The organizing unit is a complete useful understanding, not a chapter quota.

A covenant for this book

The following commitments govern the pages ahead.

1. We will introduce mathematical objects through the problems that make them necessary.

2. We will rebuild advanced ideas far enough that they can be used in judgment, not merely recognized by name.

3. We will show proofs, proof architecture, examples, and counterexamples rather than reporting that they exist.

4. We will distinguish classical mathematics, imported frameworks, FPRD synthesis, finite evidence, conjecture, and open direction.

5. We will treat exercises as opportunities to acquire mathematical control, and provide solutions or substantial hints.

6. We will expose research forks before they are closed whenever the human partner’s judgment can still matter.

7. We will preserve disagreement and correction in forms that can change later work.

8. We will not equate more pages, more tests, more citations, or more agent activity with increased understanding.

9. We will allow the architecture of the book and the direction of the program to change when reading reveals that they should.

The ambition is larger than producing a good introduction to one mathematical program. Advanced AI systems and humans are beginning to undertake endeavors whose duration, scale, and open-endedness exceed the interaction patterns for which either software tools or ordinary management practices were designed. We do not yet know the best form of those relationships. We can, however, judge them by a demanding standard: do they leave the human more free, more capable, and better able to act; do they leave the AI-mediated work more corrigible, more truthful, and better oriented; and does the partnership become able to ask and answer questions that neither side would have reached alone?

This book is one attempt to find out.

How to read this book

This is a linear book assembled from unequal monographs. The main route begins with concrete recognition problems, pauses to learn the mathematics they require, and returns to the FPRD program with new tools. Reading in order is the safest route because later synthesis chapters rely on earlier intuition as well as notation.

It is also possible to enter through one of the larger monographs:

Automata and residuals, Chapters 3–5.

For readers who want the classical finite-state foundation and the first finite-observation tower.

Topology, Chapters 6–8.

For readers who remember the vocabulary but want product topology, compactness, and inverse limits reactivated before encountering observational completion.

Presentations and recursion, Chapters 9–11.

For separating semantics, observations, finite presentations, and generated actions.

Dyck geometry, Chapters 12–14.

For context-free structure, exact stack residuals, and finite controllers over a universal recursive frame.

Hankel and information methods, Chapters 15–16.

For the linear, Boolean, communication, and streaming interpretations of observation tables.

Sewing and growth, Chapters 17–20.

For the current local-to-global theory and the research frontier.

Four proof modes

A complete proof is intended to carry the mathematical claim, subject to ordinary review. A guided proof is complete in architecture but pauses at a consequential step so the reader can reconstruct it. A proof walkthrough explains the mechanism of a large classical result without reproducing every technical lemma. A proof sketch records the essential route and points to a source when the full result would displace the book’s purpose.

Computational evidence is identified as such. It may discover a formula, challenge a proof, or establish a finite statement. It does not prove an unbounded theorem merely by checking many cases.

Colored reading devices

Exercises and solutions

Exercises appear where active work changes understanding. Some are short calculations; others complete proof steps, construct counterexamples, or ask for judgment about a definition. Every exercise points to a solution or substantial hint in the backmatter. Looking at a solution early is not a failure: the objective is to acquire a usable way of thinking.

What the book does not ask you to trust

The text does not ask the reader to infer truth from a milestone label, an AI consensus, a large test count, or the confidence of its prose. Definitions, proofs, sources, and experiments play different roles. The provenance guide in the backmatter explains the notation used to keep those roles visible.

Part I — Recognition and finite observation

1 What does it mean to recognize?

A finite automaton recognizes a language. A parser recognizes a syntax. A protocol participant recognizes a valid message. These familiar sentences hide a choice: how much of the recognizing process do we intend to observe?

If we ask only whether an input is accepted, two devices are equivalent when they accept the same words. If we also observe where parsing stopped, which continuation remains possible, or how a grammar call changes the future, the same devices may become distinguishable. Recognition is therefore not one object but a relationship among a presentation, a dynamic behavior, and an observation.

1.1 Three questions that are easy to conflate

Let $\Sigma$ be a finite alphabet and $\Sigma^*$ the set of finite words. A complete-match recognizer answers a Boolean question $$\chi(w)\in\{0,1\},$$ where $\chi(w)=1$ means that all of $w$ is recognized. The accepted language is $L=\{w:\chi(w)=1\}$.

A suffix recognizer exposes more. Given an input $w$, it may fail or return an unconsumed suffix $v$ of $w$. Complete match is now one observation of a richer behavior: success with suffix $\eps$. A set-valued recognizer may return several suffixes, recording several successful derivations while still forgetting their parse trees.

A finite grammar presentation exposes something different again. Its named nonterminals and labeled call sites generate actions on continuation behavior. Two presentations can recognize the same language while producing different internal actions. Conversely, one generated dynamic can support several observations.

The FPRD program keeps four layers separate:

1. a semantic algebra of exact recognition behaviors and their operations;

2. an observational system that identifies behaviors only to the resolution currently visible;

3. a finite presentation whose labels generate distinguished actions; and

4. a coordinate realization in which both actions and readout can be performed uniformly.

We will earn these distinctions gradually. For now the important point is that a grammar is not its language, and a state representation is incomplete if it cannot recover the recognition observation.

1.2 A small infinite family

The motivating example comes from the recursive parsing rule $$A \leftarrow a\,A\,b\;/\;\eps.$$ Read this informally as follows: try to consume an $a$, call $A$ again, and then consume a $b$; if that alternative fails at its beginning, accept the empty word. Each recursive call has a right-hand obligation: after the call returns, one more $b$ must be recognized.

At recursion depth $n$, the accumulated continuation is therefore $$K_n=\{b^n\}.$$ Here $K_n$ can be read as the exact language of words that discharge the pending right context. The family is infinite and pairwise distinguishable.

No exact quotient with finitely many states can identify all these continuations without losing behavior. It is tempting to conclude that a finite representation has failed. That conclusion confuses two claims: $$\text{finitely many exact states} \qquad\text{and}\qquad \text{a finite description of structured infinite behavior}.$$ The first is impossible here. The second is immediate: one start state $K_0$, one action $s(K_n)=K_{n+1}$, and the integer coordinate $n$ describe the whole orbit.

The readout also matters. From coordinate $n$ and input $w$, complete match is decided by the uniform rule $$\operatorname{accept}(n,w)=1 \quad\Longleftrightarrow\quad w=b^n.$$ A coordinate that merely gives each state a different real number would be an injection, not a useful recognition representation. The actions and the readout must both be controlled.

1.3 Finite observation of infinite behavior

Although the exact family $\{K_n:n\in\N\}$ is infinite, observation through input length $N$ is finite. The states $K_0,\ldots,K_N$ are individually visible: input $b^n$ distinguishes $K_n$ from every other member. Every $K_n$ with $n>N$ rejects every word of length at most $N$, so those states share one bounded-observation class. The depth-$N$ shadow therefore has $$N+2$$ classes: $N+1$ visible coordinates and one tail.

The tail is not an exact state. It is an observation-relative abstraction. At depth $N+1$, the member $K_{N+1}$ leaves the tail and becomes visible. The finite shadows form a compatible tower whose limit recovers all exact finite coordinates and a boundary behavior representing escape beyond every finite window.

This simple example contains most of the program’s questions:

• Which infinite dynamics can finite presentations generate?

• Which finite observations approximate them canonically?

• When do compatible finite shadows determine a global behavior?

• Which actions survive the passage between exact and bounded views?

• What coordinates make action and readout tractable?

• How fast do the finite shadows grow?

2 Languages, futures, and observations

We now build the vocabulary needed to turn the preceding questions into mathematics. The definitions are elementary; their arrangement is not. The same language can be viewed as a set of words, a Boolean function, an infinite table of pasts and futures, or an orbit of residual states. Each view exposes a different structure.

2.1 Words and languages

An alphabet $\Sigma$ is a finite set of symbols. The set of words of length $n$ is $\Sigma^n$, and $$\Sigma^*=\bigcup_{n\ge 0}\Sigma^n$$ contains all finite words. The unique word of length zero is $\eps$. Word concatenation is associative, has identity $\eps$, and satisfies $|uv|=|u|+|v|$.

A language is a subset $L\subseteq\Sigma^*$. Equivalently, it is its characteristic function $$\chi_L:\Sigma^*\longrightarrow\{0,1\}, \qquad \chi_L(w)=\mathbf 1[w\in L].$$ The set view makes union and concatenation natural. The function view makes observation tables and pointwise Boolean operations natural.

2.2 Left residuals: the future after a past

After reading a prefix $u$, the relevant question is which continuations still lead to acceptance.

The prefix $u$ is the past. The residual $u^{-1}L$ is its entire future language. Appending another word acts by further differentiation: $$v^{-1}(u^{-1}L)=(uv)^{-1}L.$$ Notice the order: first read $u$, then $v$, so the combined prefix is $uv$. This language-derivative viewpoint goes back to Brzozowski’s derivatives of regular expressions (Brzozowski 1964); here we apply the residual operation to arbitrary languages.

2.3 The infinite past–future table

Arrange every prefix $u$ as a row and every future $v$ as a column: $$H_L(u,v)=\mathbf 1[uv\in L].$$ This is the Boolean Hankel table of $L$. Its row indexed by $u$ is exactly the characteristic function of $u^{-1}L$. Two prefixes have the same row if and only if they have the same complete future.

The table can be cut in several ways. A fixed-length cut chooses $u\in\Sigma^m$ and $v\in\Sigma^n$. A bounded future view fixes $N$ and keeps all columns with $|v|\le N$. A bounded rectangle also restricts prefixes to $|u|\le I$.

Because there are only finitely many words of length at most $N$, the set of possible Boolean rows is finite. Thus $Q_N(L)$ is finite even when $L$ has infinitely many exact residuals.

Forgetting the coordinates with $|v|=N+1$ gives a surjection $$\rho_{N+1,N}:Q_{N+1}(L)\twoheadrightarrow Q_N(L).$$ Consequently $q_L(N)$ is nondecreasing. A finer future observation can split old classes, never merge prefixes that were already distinguished.

2.4 Observation as controlled forgetting

An observation is useful when it forgets deliberately. Complete-match language observation forgets parse trees, return locations, and alternative suffixes. Horizon-$N$ observation forgets every distinction requiring a future longer than $N$. A fixed cut forgets how rows at one length relate to rows at another.

Forgetting is not inherently a defect. It creates finite objects that can be computed, compared, minimized, and used as evidence. The danger is forgetting which information was discarded and then treating the quotient as exact.

2.5 Actions and readout

Residuals turn the set of futures into a dynamic system. Each letter $a\in\Sigma$ acts by $$D_a(R)=a^{-1}R.$$ Starting at $L$, the word $u=a_1\cdots a_k$ reaches $$D_{a_k}\cdots D_{a_1}(L)=u^{-1}L.$$ The acceptance readout is uniform: $$\operatorname{out}(R)=\mathbf 1[\eps\in R].$$ Indeed, after reading $u$, the original word belongs to $L$ exactly when $\eps\in u^{-1}L$.

This pair—letter actions plus epsilon readout—is the canonical residual recognition dynamic of a language. It may be finite or infinite. The next monograph explains why finiteness is precisely regularity and why the finite case yields the minimal deterministic automaton.

3 Finite automata, reactivated

Finite automata are familiar enough that it is easy to remember their diagrams and forget the structural reason they matter. Their essential claim is not that a machine has circles and arrows. It is that every past can be summarized by one of finitely many states in a way that preserves all future acceptance decisions.

3.1 The deterministic model

The transition extends uniquely to words: $$\begin{aligned} \delta^*(s,\eps)&=s,\\ \delta^*(s,wa)&=\delta(\delta^*(s,w),a). \end{aligned}$$ The recognized language is $$L(\mathcal A)=\{w:\delta^*(s_0,w)\in F\}.$$

The recursion says that a state is a sufficient summary of the past. If two prefixes reach the same state, appending any common future produces the same final state and hence the same acceptance decision.

3.2 Reachability and useless names

A state $s$ is reachable if $s=\delta^*(s_0,u)$ for some word $u$. Unreachable states cannot affect the recognized language and may be removed. This is the first simple distinction between a presentation and its reachable dynamic: a DFA file may name ten states while only six participate in recognition from the chosen start.

For a reachable state, a word $u$ satisfying $\delta^*(s_0,u)=s$ is an access word. A shortest access word never repeats a state along its path; otherwise the intervening loop could be deleted. A reachable automaton with $k$ states therefore reaches every state by a word of length at most $k-1$.

Reachability is not minimization. Two reachable states can still have identical futures.

3.3 State futures and distinguishability

For state $s$, define its future language $$L_s=\{v:\delta^*(s,v)\in F\}.$$ States $s,t$ are equivalent when $L_s=L_t$ and distinguishable otherwise. A word $v$ distinguishes them when exactly one of $\delta^*(s,v),\delta^*(t,v)$ is accepting.

The empty word distinguishes states with different acceptance readouts. A one-letter word may distinguish states whose immediate children have different readouts. Longer words propagate distinctions backward through the transition graph.

The standard table-filling minimization algorithm begins by separating accepting from rejecting states. It then repeatedly marks a pair $(s,t)$ when some letter $a$ sends it to the already marked pair $$\bigl(\delta(s,a),\delta(t,a)\bigr).$$ At convergence, unmarked pairs have identical futures. Chapter 4 will prove this from residuals rather than treating it as an algorithmic fact.

3.4 Products and Boolean combinations

Given DFAs $\mathcal A_1$ and $\mathcal A_2$ over the same alphabet, their product has state set $S_1\times S_2$ and acts componentwise: $$\delta((s_1,s_2),a)=(\delta_1(s_1,a),\delta_2(s_2,a)).$$ Choosing the accepting pairs realizes intersection, union, symmetric difference, or any pointwise Boolean operation on the component acceptances.

The product construction is an upper bound, not usually a minimal machine. Some pairs may be unreachable; others may have identical joint futures. This gap between a convenient presentation and the canonical reachable quotient will recur throughout the book.

3.5 What finiteness buys

A finite state set gives several kinds of leverage:

• every run can be simulated with bounded memory;

• reachability and equivalence are decidable by finite graph algorithms;

• sufficiently long runs repeat states and can be pumped;

• the family of future languages is finite; and

• bounded observations eventually stop discovering new exact futures.

These consequences explain why one might try to force an infinite recognition family into a finite quotient. The $K_n$ example teaches a different lesson: when exact futures are genuinely infinite, we should ask which pieces of this leverage survive through structure, finite shadows, or coordinates rather than identify states that the observation can still distinguish.

4 Residuals and the Myhill–Nerode mechanism

The residual construction removes accidental state names from deterministic recognition. It asks only: after this prefix, which futures are accepted? The answer produces both a canonical automaton and the exact boundary between regular and nonregular languages.

4.1 Future equivalence

For a fixed language $L$, define $$u\equiv_L u' \quad\Longleftrightarrow\quad \forall v\in\Sigma^*,\; uv\in L\iff u'v\in L.$$ Equivalently, $u^{-1}L=(u')^{-1}L$. This is an equivalence relation on $\Sigma^*$.

More is true. It is a right congruence: if $u\equiv_L u'$, then $ua\equiv_L u'a$ for every letter $a$. Indeed, for every $v$, $$uav\in L\iff u'av\in L$$ because $av$ is one of the futures quantified in the definition.

Right congruence is exactly what makes a state transition well defined on equivalence classes. Define $$[u]_L\xrightarrow{a}[ua]_L.$$ If a different representative $u'$ is chosen, right congruence gives the same target class.

4.2 The canonical residual automaton

Let $$\operatorname{Res}(L)=\{u^{-1}L:u\in\Sigma^*\}.$$ Letters act by residual differentiation, the start state is $L$, and a state $R$ is accepting exactly when $\eps\in R$.

Every residual is reachable by construction. The dynamic may still be infinite, as for square lengths or the continuation family of Chapter 1.

4.3 Finiteness is regularity

The theorem is not merely a counting result. It identifies the canonical meaning of a deterministic state: a complete future language.

4.4 Distinguishing words and proof by residual growth

To prove that a language is nonregular, it is enough to exhibit infinitely many prefixes with pairwise different residuals. For each pair one supplies a future accepted after one prefix and rejected after the other.

Residual separation resembles a pumping argument but is often more direct. It states exactly what a finite-state summary would have to forget and supplies a future showing that the forgotten distinction still matters.

4.5 Presentation states versus residual states

A deterministic implementation may carry more state than the residual dynamic. Its state-to-residual map is a quotient. This fact separates three questions:

1. Is the implementation reachable?

2. Is it behaviorally minimal for its language?

3. Does its presentation carry additional named structure that we intend to preserve even when language observation forgets it?

The second question has the residual automaton as its exact answer. The third is one reason FPRD does not identify a finite grammar presentation with the minimal machine of its observed language.

5 Finite horizons and observational shadows

Residual equality asks whether two prefixes agree on every possible future. Finite observation replaces “every” by “every future of length at most $N$.” The resulting quotients are always finite and form a tower that approaches exact residual behavior.

5.1 Horizon equivalence

Define $$u\equiv_N u' \quad\Longleftrightarrow\quad \forall v\;( |v|\le N\Rightarrow (uv\in L\iff u'v\in L)).$$ The equivalence class of $u$ is its row $B_N(u)$ from Chapter 2. The quotient is $Q_N(L)$.

Exact residual equality implies $u\equiv_Nu'$ for every $N$. Conversely, if $u\equiv_Nu'$ for all $N$, then any particular future $v$ is covered once $N\ge |v|$, so $u$ and $u'$ have the same residual. Exact equality is thus the intersection of all horizon equivalences.

The relation $\equiv_{N+1}$ refines $\equiv_N$. Restriction gives a surjective bond $$Q_{N+1}(L)\twoheadrightarrow Q_N(L).$$ Surjectivity is literal: every depth-$N$ row is the restriction of the depth-$(N+1)$ row belonging to the same prefix.

5.2 A graded action rather than a same-level machine

Appending a letter consumes one unit of future horizon. If $B_{N+1}(u)=B_{N+1}(u')$, then for every $|v|\le N$, $$uav\in L\iff u'av\in L,$$ so $B_N(ua)=B_N(u'a)$. Each letter therefore induces a well-defined map $$Q_{N+1}(L)\longrightarrow Q_N(L).$$

It does not generally induce a map $Q_N\to Q_N$. Two prefixes may agree on all futures of length at most $N$ while their $a$-children disagree on a future of length $N$; that disagreement corresponds to a future of length $N+1$ at the parent level.

5.3 How far must prefixes be searched?

The quotient $Q_N(L)$ counts all bounded futures, including ones first exposed by very long prefixes. Define the bounded rectangle $$X[I,N]=\{B_N(u):|u|\le I\}$$ and its size $$G_L(I,N)=|X[I,N]|.$$ For fixed $N$, this count grows with $I$ and eventually reaches $q_L(N)$.

The minimum exists because $Q_N(L)$ is finite and every class has at least one literal prefix representative. The number $q_L(N)$ asks how many bounded futures exist. The number $a_L(N)$ asks how late the last of them first appears.

If $L$ has a reachable $k$-state DFA, every residual state has an access word of length at most $k-1$. Every bounded row is a projection of some residual, so $$a_L(N)\le k-1$$ for every horizon.

Prefix counting gives a lower bound in the other direction. If $d=|\Sigma|$, there are at most $$1+d+d^2+\cdots+d^{a_L(N)}$$ prefixes in the access ball. Therefore $$q_L(N)\le\sum_{j=0}^{a_L(N)}d^j.$$ For unary languages this simplifies to $q_L(N)\le a_L(N)+1$.

5.4 Accessibility and distinguishability in a minimal DFA

For a finite minimal DFA, two classical depths sit on the two axes of the rectangle $G_L(I,N)$.

The accessibility degree is the maximum, over states, of the length of a shortest access word. Once horizon $N$ is large enough to distinguish all residual states, $a_L(N)$ equals this degree.

The distinguishability degree is the maximum, over distinct state pairs, of the length of a shortest separating future. The first horizon at which $q_L(N)$ reaches the number of residual states is exactly this degree (with the one-state convention handled separately).

Thus the two-dimensional observation rectangle extends two familiar finite automaton notions. Before saturation it records partial coverage; for nonregular languages it continues indefinitely.

5.5 Why one observed plateau is delicate

Because $q_L(N)$ is nondecreasing, equality $q_L(N)=q_L(N+1)$ means the restriction bond is a bijection. This turns out to be much stronger than seeing the same number of rows in two finite samples of prefixes. A global adjacent plateau ranges over every prefix and will later force a right congruence. A finite membership table cannot certify that no longer prefix introduces a new row unless an independent state bound or equivalent guarantee is available.

This distinction is central to active automata learning. A finite observation table can suggest a machine, but an equivalence query or other completeness mechanism is needed to know that the table has captured the whole language (Angluin 1987). The exact global statement appears as Theorem 18.1.

Part II — Topology for infinite behavior

6 Topological spaces: nearness without distance

Topology studies which distinctions can be made by local observation and how those distinctions behave under limits. It can be introduced as geometry without measurements, but for recognition dynamics a different intuition is more useful: a neighborhood specifies a finite amount of information that we insist on observing, while leaving the rest unresolved.

We begin far from inverse limits. The objective is to recover a working feel for open and closed sets, continuity, and convergence across several kinds of space.

6.1 Open sets as permitted observations

An open set is not intrinsically fuzzy or boundaryless. It is one of the subsets the topology permits us to recognize locally. The axioms say that a choice among any family of observable alternatives is observable (union), and that finitely many simultaneous observational requirements can be combined (finite intersection).

Why only finite intersections? In the real line, every interval $(-1/n,1/n)$ is open, but their infinite intersection is $\{0\}$, which is not open. Demanding infinitely many increasingly precise conditions can identify an exact point even though no finite stage does.

6.2 Closed sets and limits

A set $C\subseteq X$ is closed when its complement $X\setminus C$ is open. Closed sets satisfy the dual laws: $\varnothing$ and $X$ are closed, arbitrary intersections of closed sets are closed, and finite unions of closed sets are closed.

In metric spaces, closed sets are exactly the sets containing all limits of their convergent sequences. In arbitrary spaces this sequential criterion can fail, but the intuition remains useful: closedness prevents a set from losing limit points visible to the topology.

6.2.1 How can a set be both open and closed?

A clopen set is both open and closed. There is no contradiction: open and closed are not mutually exclusive adjectives like finite and infinite. They describe a set and its complement. A set is clopen precisely when it and its complement are both observable as open alternatives.

The sets $\varnothing$ and $X$ are always clopen. In a discrete space every set is clopen. In the usual real line, no other sets are clopen because $\mathbb R$ is connected.

Clopen sets will be central for finite observations. In a product of discrete Boolean coordinates, fixing finitely many coordinate values defines a clopen cylinder. One can decide both membership and nonmembership using the same finite observation.

6.3 Bases and neighborhoods

Listing every open set is often impractical. A basis is a collection $\mathcal B$ of subsets such that every open set is a union of basis elements and, whenever $x\in B_1\cap B_2$, some $B_3\in\mathcal B$ satisfies $x\in B_3\subseteq B_1\cap B_2$.

Open intervals form a basis for $\mathbb R$. Open balls form a basis for a metric space. Finite-coordinate cylinders form a basis for the product spaces we will use.

A neighborhood of $x$ is a set containing an open set that contains $x$. Neighborhood language lets us state local properties without choosing a particular basis.

The second formulation is observational: $x$ lies in the closure of $A$ when no finite local observation around $x$ can exclude all of $A$.

The recognition orbit $\{K_n:n\in\N\}$ behaves similarly under bounded-input observation. As $n$ escapes every fixed horizon, the states converge to a boundary behavior that rejects every finite word. The boundary is not one of the $K_n$, just as $0$ is not one of the positive reciprocals.

6.4 Continuity

The inverse-image definition is chosen because inverse images preserve arbitrary unions and finite intersections automatically. Conceptually, a continuous map cannot require infinitely more input precision to decide a finite output observation. Every observable distinction in the target pulls back to an observable distinction in the source.

6.5 Convergence and separation

A sequence $(x_n)$ converges to $x$ if every neighborhood of $x$ contains all but finitely many $x_n$. In a metric space this agrees with the familiar $d(x_n,x)\to0$.

Limits need not be unique in an arbitrary topology. In the indiscrete space, every sequence converges to every point because the only neighborhood condition is eventual membership in $X$. A Hausdorff space separates distinct points by disjoint neighborhoods; in such spaces sequence limits are unique.

All finite discrete spaces are Hausdorff. Their products are Hausdorff. The compact recognition spaces constructed later therefore retain ordinary distinctness even though their topology is generated by finite observations.

7 Products and compactness

Recognition behavior is naturally coordinatewise. A language assigns one Boolean value to every word. A bounded observation sees finitely many of those values. Product topology is precisely the topology in which fixing finitely many coordinates describes a basic observation.

Compactness then supplies the global principle we need: when finite pieces of information remain mutually compatible, they cannot drift away without leaving a global limit point.

7.1 The product topology

Let $(X_i)_{i\in I}$ be topological spaces. Their Cartesian product $$X=\prod_{i\in I}X_i$$ consists of tuples $x=(x_i)_{i\in I}$. For each coordinate there is a projection $\pi_i(x)=x_i$.

A basis element restricts finitely many coordinates and leaves all others free: $$U=\prod_{i\in I}U_i, \qquad U_i\subseteq X_i\text{ open}, \qquad U_i=X_i\text{ for all but finitely many }i.$$ Such a set is often called a cylinder.

Why finitely many restrictions? The product topology is designed so that an open observation requests only finitely much coordinate information. If infinitely many exact coordinate conditions were basic open sets, convergence would become much stricter and finite observations would no longer generate the topology.

The same idea works when coordinates are indexed by words rather than natural numbers. Since $\Sigma^*$ is countable, choose any enumeration $w_0,w_1,\ldots$. A language becomes a point $$\chi_L\in 2^{\Sigma^*}.$$ A cylinder prescribes membership for finitely many words. The bounded-input topology uses the especially natural cofinal family of cylinders fixing all words through a given length.

7.2 Convergence in a product

A sequence $x^{(n)}$ in a product converges to $x$ exactly when it converges in every coordinate, provided the index set is countable and we use sequences. For discrete coordinate spaces, coordinate convergence means eventual equality.

Thus languages $L_n$ converge to $L$ in $2^{\Sigma^*}$ when, for every fixed word $w$, membership $w\in L_n$ eventually agrees with $w\in L$. Equivalently, for every length bound $N$, the languages eventually agree on every word of length at most $N$.

7.2.1 An ultrametric for bounded observation

The topology can be metrized directly. For distinct languages $L,L'$, let $$n(L,L')=\min\{|w|:\mathbf 1[w\in L]\ne\mathbf 1[w\in L']\}$$ and define $$d(L,L')=2^{-n(L,L')}, \qquad d(L,L)=0.$$ Then $d(L,L')<2^{-N}$ means the two languages agree through a corresponding finite horizon, with the exact indexing convention adjusted at equality.

This metric is an ultrametric: $$d(L_1,L_3)\le \max\{d(L_1,L_2),d(L_2,L_3)\}.$$ If $L_1$ and $L_2$ agree through one horizon and $L_2$ and $L_3$ agree through another, then $L_1$ and $L_3$ agree through the smaller of the two horizons. Ultrametric balls are clopen, reflecting the finite-decision nature of bounded observations.

7.3 Compactness from open covers

In Euclidean space, closed bounded sets are compact by the Heine–Borel theorem. But compactness is not synonymous with closed-and-bounded outside that setting. The open-cover definition is topological and travels to product spaces and inverse limits.

Compactness often turns an infinite family of local possibilities into a finite witness for a global statement. If each point has some neighborhood on which a property is controlled, a finite subcover can sometimes make the control uniform. If an infinite collection of closed constraints is finitely compatible, compactness can force a point satisfying all of them.

7.4 Why compactness resembles finiteness

Every finite space is compact: from an open cover, choose one set containing each point. Compact spaces may be infinite, but open-cover arguments allow many finite-space proofs to survive after replacing literal enumeration by a finite subcover or finite-intersection argument.

Compactness is useful for recognition dynamics for three recurring reasons.

1. An infinite orbit may acquire boundary points without becoming uncontrollably large; its closure inside a compact behavior space remains compact.

2. A compatible family of finite observations can be realized by a global behavior when the corresponding closed constraints have the finite intersection property.

3. Continuous actions on a dense orbit extend uniquely in situations where their finite observational behavior is coherent.

Compactness does not imply finite-state recognition. The Cantor space $2^{\N}$ is compact and uncountable. The closure of an infinite residual orbit can be compact while the language remains nonregular. Compactness is a form of global control, not a disguised state bound.

7.5 Compactness of a countable product of finite spaces

The full Tychonoff theorem states that arbitrary products of compact spaces are compact. Its general proof requires a choice principle. Our principal behavior spaces are countable products of finite discrete spaces, where a direct diagonal argument is available.

Since $\Sigma^*$ is countable and each coordinate $\{0,1\}$ is finite, $2^{\Sigma^*}$ is compact. It is also Hausdorff, totally disconnected, and metrizable by bounded-input agreement.

7.6 Closed subspaces and orbit closures

A closed subset of a compact space is compact. To see this, cover the closed set $C$ by open sets in $X$ and add the open complement $X\setminus C$; a finite subcover of $X$ leaves a finite subcover of $C$ after discarding the complement.

For a language $L$, its residual orbit $$O_L=\{u^{-1}L:u\in\Sigma^*\}$$ sits inside the compact behavior space $2^{\Sigma^*}$. Its closure $$X_L=\overline{O_L}$$ is therefore compact. When $O_L$ is finite it is already closed. When it is infinite, the closure may add limit behaviors.

The orbit is dense in $X_L$ by the definition of closure. Density means every finite observation of a completion point is matched by some literal residual. It does not mean every completion point is a residual.

8 Inverse limits: assembling compatible shadows

An inverse limit is a space of globally compatible finite views. The phrase can sound forbidding because it belongs to category theory and topology, but the basic construction is concrete: take one observation at every resolution and require that forgetting detail gives the observation chosen at the coarser resolution.

8.1 Inverse systems

An inverse sequence consists of spaces $$X_0\xleftarrow{\rho_{1,0}}X_1 \xleftarrow{\rho_{2,1}}X_2 \xleftarrow{}\cdots.$$ For $m>n$, write $$\rho_{m,n}=\rho_{n+1,n}\circ\cdots\circ\rho_{m,m-1}.$$ The maps are called bonding maps because they state how a fine view restricts to a coarse one.

The construction is characterized by a mapping property. This matters because it tells us that the coordinate formula is canonical rather than an arbitrary encoding.

The inverse limit is not a mysterious point “at infinity.” It is the set of all coherent choices across every finite level.

8.2 Why compatibility matters

Choosing arbitrary $x_n\in X_n$ produces an element of the product but not necessarily an element of the inverse limit. The thread might claim that the first two bits are $01$ at one level and that the first three bits are $111$ at the next. Each finite object is legal; the family is jointly impossible.

This distinction becomes essential in local-to-global reasoning. A list of individually realizable finite observations need not have a common global realization. Bonding equations are the first consistency conditions. Later, literal cut compatibility will play the same role across two axes.