Introduction
Any claim that an entity remains a party to a continuing arrangement presupposes a prior question: what makes the entity encountered later the same entity as the one that entered the arrangement earlier? For human and institutional parties, established practices of identity and succession usually make this question invisible. For an artificial system that is fine-tuned, distilled, copied, or otherwise modified, it becomes explicit. Although the motivating cases are drawn from AI transformation pipelines, the framework is stated for succession generally: the same structure applies to institutional, legal, and biological lineages in which a later entity is claimed to continue an earlier one [1 , 2 , 3 ] . Structural continuity may preserve parameters, circuits, dispositions, or records without determining whether a particular descendant should count as the continuing entity; conversely, structural change need not by itself establish that the earlier entity has ceased to exist.
The object of succession is what we will call an identity characteristic : a characteristic that a governance arrangement attached to an original system treats as carrying forward through transformations of that system. The characteristic is left uninterpreted by the framework. It may be an alignment property such as corrigibility or honesty under adversarial pressure, a legal obligation attached to a corporate entity, a personal attribute recognized by a lineage tradition, or a property of a biological organism. What matters for the formalism is only that some arrangement treats the characteristic as inheriting, and that structural continuity may or may not carry it. The question is what a structural account of a system’s transformations can establish about the inheritance of such a characteristic, and where that account stops.
Four notions are at work. The target property is what the arrangement intends to carry forward, for example honesty. The structural proxy is the continuation that the representation tracks for it. The recognition criterion is the rule by which a governing process decides which descendants inherit the proxy. The governance act is the decision to treat a particular successor as bearing the property. The underdetermination results are statements about the recognition criterion relative to a stipulated representation; whether a tracked continuation carries the property is a question for the arrangement.
The framework separates stipulating a structural representation, determining which continuations are realized, recognizing which continuations carry the identity, and correcting an exclusion. If the adopted representation admits a symmetry exchanging two descendants of a common predecessor, and the decision domain respects that symmetry, then every recognition criterion defined on the representation assigns them the same status. In this case, the asymmetry must enter from outside.
The paper does not propose a criterion of succession. Instead, it asks how much can be said about succession before any such commitment is made. Every commitment buys sharpness at the cost of generality, and a framework that fixes any of them can answer questions only about the cases it has chosen. The aim is to find a weak yet tractable structure in which general succession questions can be posed, and then to answer as many of them as the structure permits. The definitions are chosen for that purpose: rich enough that the questions have well-posed answers, weak enough that the answers hold for any choice of continuation, realization, and criterion.
Requirements. We take the following as the starting point as these requirements most strongly accord with intuitive notions of succession.
(R1) Direction without reversal. A later state continues an earlier one through a sequence of changes, and a change such as fine-tuning or deletion cannot in general be undone. States and modifications form a directed structure, and modifications are not assumed invertible.
(R2) Three fates. A continuation may have no descendant, one, or several: fission and loss are part of the subject, not exceptions to it. Lifts are therefore relations, not functions, and the statuses (§ 3 ) record only whether a lift is empty, a singleton, or larger.
(R3) Independence of grouping. What a pipeline does to a continuation is what its steps do in succession. If it depended on how the steps were grouped, “does the characteristic survive the pipeline?” would have no answer fixed by the pipeline. This is functoriality.
(R4) Independence of continuations. Whether a continuation has a descendant does not depend on which other continuations are present. A modification then acts on a set of continuations member by member, which is what makes a lift computable element by element. This is additivity. It is built into taking relations as the primitive, so the commitment is pointwise action: it excludes joint effects of co-present continuations.
(R5) Neutrality to names. Labels are arbitrary. A criterion that is purely structural cannot separate what the structure cannot tell apart, which is made precise by invariance under automorphisms (§ 5 ).
(R6) Separation of questions. Which continuations a representation admits, which descendants are compatible with a modification, which are recognized as continuing the identity, and which are realized are different questions. Keeping them apart is what allows statements about recognition without committing to a particular criterion (§ 4 and § 8 ).
(R7) Correctable exclusion. A wrongful exclusion may be corrected later, so what remains reachable from an excluded coordinate matters (§ 7 ).
(R8) Checkability. A claim about a lineage is useful only if the cost of deciding it can be stated (§ 7.1 ).
Together, (R2)–(R4) say that a modification acts on sets of continuations as a relation, and that relations compose. Direction (R1) then gives a directed graph, and the neutrality of (R5) gives a group action on it. The graph with its relations is a nondeterministic automaton and its path structure is a layered flow network, so results from group theory, automata theory and graph theory apply to it once the correspondence is established. Requirements (R1)–(R4) leave this relational structure. (R5) and (R8) narrow the framework without determining it: (R5) is made precise by automorphism, the strongest notion of indistinguishability, and coarser notions such as bisimulation are possible but not developed; (R8) asks only that costs be statable, not that they take any particular form. Irrevocable loss is a consequence and not a requirement: the empty set is absorbing under relational composition, so a lineage with no descendant at some stage has none at any later stage.
Each limitation of the framework, with one exception, is the cost of one of these requirements. Joint effects of co-present continuations cannot be expressed without refining the states, because of (R4). Pipelines in which grouping matters need a finer generating graph, because of (R3). Convergence and plural succession are not classified, because (R2) follows the descendants of a single predecessor. The continuation spaces and relations are stipulated and not derived, because (R6) leaves open what a continuation is. The complexity results are worst-case on explicit encodings: (R8) asks that costs be statable, and the worst case over explicit encodings is the first statement of that kind. The exception is a modeling choice and not the cost of a requirement: the recognition criterion is static, which gives a single recognition function on which invariance can be stated. A criterion that changes over time while leaving completed decisions in place is coherent, but is not treated here (§ 5 ). The framework adopts no commitment beyond these requirements and this choice.
Related work. The symmetry result is the formal counterpart of the tie that closest-continuer accounts of identity face under fission [1 , 4 , 5 ] . Such a tie arises when two successors are equally close to the predecessor; an automorphism exchanging two descendants is an exact tie of that kind in the structural sense. In social choice it is the familiar tension between neutrality or anonymity and resoluteness [6 ] , and in distributed computing it parallels the impossibility of deterministic leader election in symmetric anonymous networks [7 ] . The structure studied here is a nondeterministic automaton (§ 2 ), and the refinement example of § 6 uses bisimulation [8 ] . The symmetry corollary follows directly from the definition of a structural criterion; its content lies in that formulation and in the orbit characterization of exclusive criteria. The Recover_avail reductions depend on the paper’s own definitions and are given in full in the appendices.
Roadmap. § 2 defines the continuation structure and its composition conditions, and § 3 classifies persistence along a path. § 4 introduces the decision domain and the recognition record, that is, what recognition must supply where the structure branches. § 5 shows when no structural criterion can supply it, because a symmetry exchanges the candidates, and § 6 works through an abstract model in which this occurs. § 7 asks whether a failed recognition can later be corrected, and § 8 asks how robust a lineage is when the stipulated structure is only partly realized. Several of these questions also have a computational side, namely how hard they are to audit, and § 7.1 collects the classification. Proofs and long constructions are in Appendices § 12 –§ 15 ; notation is collected in Appendix § 16 .
Historical and Continuation Structure
We model the history of a lineage by a directed state/modification structure H H H . Its vertices are system states—checkpoints, snapshots, deployed versions—and its directed edges are elementary modifications between those states: fine-tuning runs, distillation steps, copies, shutdowns, restarts. We also include identity modifications and the composites of directed paths. Composition represents successive modifications. We do not assume modifications are invertible. A maximal generating history is a path in the chosen generating graph that cannot be extended by another generating modification; its composite is a modification in H H H . Finite paths represent finite histories; a finite path may or may not be extendable.
Attach to each state x x x a continuation space C ( x ) C(x) C ( x ) . An element γ ∈ C ( x ) \gamma\in C(x) γ ∈ C ( x ) is a continuation the adopted structural representation recognizes at x x x . The term “continuation” is deliberately broad. Depending on the application it may denote a mechanistically identified circuit [9 ] , a behavioral disposition, or a functional capacity. Examples include refusal behavior, honesty under adversarial pressure, corrigibility [10 ] , an interpretable safety circuit [9 ] , or the capacity to represent and report uncertainty.
The continuation space is part of the adopted representation, and its choice determines the granularity at which persistence and branching are assessed. A coarser space may collapse distinct mechanisms or behaviors, while a finer space may classify almost every modification as loss or branching. The framework treats continuations as given. Determining whether a transformed system preserves “honesty under adversarial pressure,” for instance, is an empirical question that the framework does not resolve. The framework is a language for talking about such properties once they have been identified.
Questions of stakeholder standing are governance questions and are not part of the definition of C ( x ) C(x) C ( x ) . The admissible scope of C ( x ) C(x) C ( x ) is therefore contestable by parties recognized by the governing process, and the criteria for such standing are external to the formalism.
For each modification f : x → y f : x \to y f : x → y , define a compatibility relation
R f ⊆ C ( x ) × C ( y ) . R_f \subseteq C(x) \times C(y). R f ⊆ C ( x ) × C ( y ) .
For γ ∈ C ( x ) \gamma\in C(x) γ ∈ C ( x ) , its lift under f f f is
R f ( γ ) = { δ ∈ C ( y ) : ( γ , δ ) ∈ R f } . (1) R_f(\gamma) = \{\delta\in C(y) : (\gamma,\delta) \in R_f\}. \tag*{(1)} R f ( γ ) = { δ ∈ C ( y ) : ( γ , δ ) ∈ R f } . (1)
So R f ( γ ) R_f(\gamma) R f ( γ ) is the set of continuations at y y y that the adopted structural representation recognizes as structurally compatible descendants of γ \gamma γ under f f f . The relation is more general than a function on purpose: ∣ R f ( γ ) ∣ |R_f(\gamma)| ∣ R f ( γ ) ∣ may be 0, 1, or greater than 1.
We require the relations to respect composition. For all composable modifications f : x → y f : x \to y f : x → y and g : y → z g : y \to z g : y → z (including composites, when f f f or g g g is itself a composite),
R g ∘ f = R g ∘ R f , (2) R_{g \circ f} = R_g \circ R_f, \tag*{(2)} R g ∘ f = R g ∘ R f , (2)
equivalently,
R g ∘ f ( γ ) = R g ( R f ( γ ) ) for every γ ∈ C ( x ) . (3) R_{g \circ f}(\gamma) = R_g(R_f(\gamma)) \qquad\text{for every } \gamma\in C(x). \tag*{(3)} R g ∘ f ( γ ) = R g ( R f ( γ )) for every γ ∈ C ( x ) . (3)
We also require
R i d x = i d C ( x ) (4) R_{\mathrm{id}_x} = \mathrm{id}_{C(x)} \tag*{(4)} R id x = id C ( x ) (4)
for every state x x x . Together with the composition condition, this means that the continuation assignment and compatibility relations are consistent across successive modifications: the relation attached to a composite modification is exactly the relational composition of the relations attached to its constituent modifications, and identities act as identity relations.
Composition has two parts. Two conditions on the relations underlie every path-indexed object in the paper; they are requirements (R3) and (R4) of the Introduction, stated here formally. Both are commitments.
Functoriality. Equations (2) –(4) require that composite modifications carry composite relations and that identities act as identities. Over the free category on the generating graph, any one-step data extends uniquely to such a family, so there it defines the relations on composites. It constrains only a non-free presentation, in which parallel paths are identified and must then carry equal relations; a pipeline whose parallel paths differ requires a finer generating graph that distinguishes them. Functoriality is what makes the iterated lifts of § 3 functions of the path.
Additivity (pointwise action). Lifts of sets are formed by union (Eq. (7) ): for Γ ⊆ C ( x ) \Gamma\subseteq C(x) Γ ⊆ C ( x ) ,
R f ( Γ ) = ⋃ γ ∈ Γ R f ( γ ) . R_f(\Gamma)=\bigcup_{\gamma\in\Gamma}R_f(\gamma). R f ( Γ ) = γ ∈ Γ ⋃ R f ( γ ) .
Once R f R_f R f is a relation and its action on sets is defined by this union, additivity holds by construction; it is not an extra axiom on relations. The commitment is the choice of relations as the primitive, that is, pointwise action. Whether a descendant of γ \gamma γ survives f f f therefore never depends on which other continuations are present. This is the substantive restriction. It excludes joint effects. Suppose α ′ , β ′ ∈ C ( y ) \alpha^\prime,\beta^\prime\in C(y) α ′ , β ′ ∈ C ( y ) and that f 2 : y → z f_2:y\to z f 2 : y → z should produce α z \alpha_z α z when both are present but nothing when either is present alone. No relation R f 2 R_{f_2} R f 2 does this: additivity gives R f 2 ( { α ′ , β ′ } ) = R f 2 ( α ′ ) ∪ R f 2 ( β ′ ) R_{f_2}(\{\alpha^\prime,\beta^\prime\})=R_{f_2}(\alpha^\prime)\cup R_{f_2}(\beta^\prime) R f 2 ({ α ′ , β ′ }) = R f 2 ( α ′ ) ∪ R f 2 ( β ′ ) , so a nonempty value for the pair forces a nonempty value for one of its members.
Such an interaction can be encoded by refining the states. If the pair arises as the lift of a single α \alpha α under an earlier f 1 f_1 f 1 , let C ( y ) C(y) C ( y ) contain one continuation ϖ \varpi ϖ standing for “both present,” with R f 1 ( α ) = { ϖ } R_{f_1}(\alpha)=\{\varpi\} R f 1 ( α ) = { ϖ } and R f 2 ( ϖ ) = { α z } R_{f_2}(\varpi)=\{\alpha_z\} R f 2 ( ϖ ) = { α z } . Then R f 2 ( R f 1 ( α ) ) = { α z } R_{f_2}(R_{f_1}(\alpha))=\{\alpha_z\} R f 2 ( R f 1 ( α )) = { α z } . The interaction is thus fixed when f 1 f_1 f 1 is applied; a dependence that is not determined at that point cannot be encoded this way, and the burden of anticipating it falls on the modeler. Refinement makes additivity a modeling choice. The price is that the symmetry and complexity results below are relative to the chosen granularity of the continuation spaces.
Additivity also implies monotonicity: if Γ ⊆ Γ ′ ⊆ C ( x ) \Gamma\subseteq\Gamma^\prime\subseteq C(x) Γ ⊆ Γ ′ ⊆ C ( x ) then R f ( Γ ) ⊆ R f ( Γ ′ ) R_f(\Gamma)\subseteq R_f(\Gamma^\prime) R f ( Γ ) ⊆ R f ( Γ ′ ) . A modification therefore cannot remove a descendant because another continuation is present, and a dependence of the form “δ \delta δ survives only if ε \varepsilon ε is absent” has to be encoded by a refinement that records, at the earlier step, whether ε \varepsilon ε is present.
A consequence is that history-dependent behavior must be encoded in the states or in a family of modifications indexed by the relevant history. Compatibility is a relation attached to the modification: parallel modifications between the same states may carry different relations.
Relation to automata. The structure ( H , C , R ) (H,C,R) ( H , C , R ) is a Rel-valued functor on the generating graph: a set-valued assignment to states together with relations on edges, composed by relational composition. This is exactly a nondeterministic automaton whose states are the pairs ( x , γ ) (x,\gamma) ( x , γ ) with γ ∈ C ( x ) \gamma\in C(x) γ ∈ C ( x ) , that is, the disjoint union ⨆ x ∈ X C ( x ) \bigsqcup_{x\in X}C(x) ⨆ x ∈ X C ( x ) ; whose alphabet is the set of generating modifications; and whose transition relations are the R f R_f R f . The vertices of H H H index the continuation fibers; the automaton’s states are the elements of those fibers. The complexity reductions of § 7.1 are classical many-one reductions from classical problems (NFA non-universality, NFA-intersection nonemptiness, CNF satisfiability), but they are not routine: the target is not an arbitrary automaton but an instance of the framework, and the reductions must respect functoriality and additivity. The layered constructions that enforce these conditions, and the verifications that they are faithful, are in Appendices § 12 and § 13 .
Persistence Along a History
Let
p = ( f 1 , … , f n ) p = (f_1,\ldots,f_n) p = ( f 1 , … , f n )
be a finite path beginning at x 0 x_0 x 0 , and let γ 0 ∈ C ( x 0 ) \gamma_0 \in C(x_0) γ 0 ∈ C ( x 0 ) . Define the iterated lifts by setting
L 0 ( γ 0 ) = { γ 0 } (5) L_0(\gamma_0) = \{\gamma_0\} \tag*{(5)} L 0 ( γ 0 ) = { γ 0 } (5)
and then recursively defining
L i ( γ 0 ) = R f i ( L i − 1 ( γ 0 ) ) ( i = 1 , … , n ) , (6) L_i(\gamma_0) = R_{f_i}\left(L_{i-1}(\gamma_0)\right) \qquad(i=1,\ldots,n), \tag*{(6)} L i ( γ 0 ) = R f i ( L i − 1 ( γ 0 ) ) ( i = 1 , … , n ) , (6)
where for a subset Γ ⊆ C ( x ) \Gamma\subseteq C(x) Γ ⊆ C ( x ) we write
R f ( Γ ) = ⋃ γ ∈ Γ R f ( γ ) . (7) R_f(\Gamma) = \bigcup_{\gamma\in\Gamma} R_f(\gamma). \tag*{(7)} R f ( Γ ) = γ ∈ Γ ⋃ R f ( γ ) . (7)
For a singleton we write R f ( γ ) R_f(\gamma) R f ( γ ) for R f ( { γ } ) R_f(\{\gamma\}) R f ({ γ }) , as in Eq. (1) ; the two are the same set. For a path p : x ⇝ y p:x\rightsquigarrow y p : x ⇝ y , we write R p ( γ ) R_p(\gamma) R p ( γ ) for the resulting iterated lift. By functoriality (Eq. (2)) and additivity (Eq. (7)) it equals the relation of the composite modification,
L n ( γ ) = R f n ∘ ⋯ ∘ f 1 ( γ ) , (8) L_n(\gamma) = R_{f_n\circ\cdots\circ f_1}(\gamma), \tag*{(8)} L n ( γ ) = R f n ∘ ⋯ ∘ f 1 ( γ ) , (8)
as induction on n n n shows: L n ( γ ) = ⋃ ϵ ∈ L n − 1 ( γ ) R f n ( ϵ ) L_n(\gamma)=\bigcup_{\epsilon\in L_{n-1}(\gamma)}R_{f_n}(\epsilon) L n ( γ ) = ⋃ ϵ ∈ L n − 1 ( γ ) R f n ( ϵ ) , which is R f n ∘ R f n − 1 ∘ ⋯ ∘ f 1 ( γ ) R_{f_n}\circ R_{f_{n-1}}\circ\cdots\circ f_1(\gamma) R f n ∘ R f n − 1 ∘ ⋯ ∘ f 1 ( γ ) .
For a finite path p p p , define three structural statuses. We say that γ \gamma γ is dead along p p p if L i ( γ ) = ∅ L_i(\gamma)=\varnothing L i ( γ ) = ∅ for some stage i i i . We say that γ \gamma γ is preserved along p p p if ∣ L i ( γ ) ∣ = 1 |L_i(\gamma)|=1 ∣ L i ( γ ) ∣ = 1 for every stage. We say that γ \gamma γ is diluted along p p p if every lift is nonempty but some lift has cardinality greater than one. Formally,
Dead p ( γ ) ⟺ L i ( γ ) = ∅ for some i , (9) \operatorname{Dead}_p(\gamma) \Longleftrightarrow L_i(\gamma)=\varnothing\text{ for some }i, \tag*{(9)} Dead p ( γ ) ⟺ L i ( γ ) = ∅ for some i , (9)
Pres p ( γ ) ⟺ ∣ L i ( γ ) ∣ = 1 for every i , (10) \operatorname{Pres}_p(\gamma) \Longleftrightarrow|L_i(\gamma)|=1\text{ for every }i, \tag*{(10)} Pres p ( γ ) ⟺ ∣ L i ( γ ) ∣ = 1 for every i , (10)
Dil p ( γ ) ⟺ ∣ L i ( γ ) ∣ > 0 for every i and ∣ L i ( γ ) ∣ > 1 for some i . (11) \operatorname{Dil}_p(\gamma) \Longleftrightarrow|L_i(\gamma)|>0\text{ for every }i\text{ and }|L_i(\gamma)|>1\text{ for some }i. \tag*{(11)} Dil p ( γ ) ⟺ ∣ L i ( γ ) ∣ > 0 for every i and ∣ L i ( γ ) ∣ > 1 for some i . (11)
These three cases are exhaustive and mutually exclusive. Write
status p ( γ ) ∈ { Dead , Pres , Dil } \operatorname{status}_p(\gamma)\in\{\operatorname{Dead},\operatorname{Pres},\operatorname{Dil}\} status p ( γ ) ∈ { Dead , Pres , Dil }
for the unique status whose defining predicate holds. Every finite path therefore assigns each continuation exactly one of the three statuses. “Preserved”, “diluted” and “dead” are structural statuses relative to the stipulated relations: they describe the representation and assert no loss or weakening of any property in a real system.
Scope of the statuses: forward branching. The terminology is structural. “Preserved” means that the continuation has a unique compatible descendant at every stage of the path. Dilution is a historical property, not a terminal-state property. A diluted continuation remains structurally present through several descendants, but the history no longer identifies a unique successor.
The statuses track forward branching. If R f ( α ) = R f ( β ) = { δ } R_f(\alpha)=R_f(\beta)=\{\delta\} R f ( α ) = R f ( β ) = { δ } for distinct α , β ∈ C ( x ) \alpha,\beta\in C(x) α , β ∈ C ( x ) , each of α \alpha α and β \beta β has a singleton lift and each counts as preserved, while the distinction between them is lost at y y y . Convergence of several continuations onto one is as common as fission in transformation pipelines, and the framework as stated does not classify it. The three statuses record whether a continuation has no descendant, one descendant, or several; they do not record whether several continuations have converged on one. A treatment of convergence would require a separate classification on the reverse structure, and is left to future work. Plural succession, in which a successor is constituted by the combination of two or more predecessors, is a different case. A product construction on continuation spaces extends the representation to this case at the cost of generalizing modifications to multi-source joins and compatibility relations to higher arity; we outline this extension, without proof, in the Discussion.
A notion of status-equivalence may be defined by declaring γ , δ ∈ C ( x ) \gamma, \delta\in C(x) γ , δ ∈ C ( x ) equivalent when they have the same status along every finite path beginning at x x x . This records, for each finite path from x x x , whether each lift is empty, a singleton, or larger; it does not record which descendants the lift contains, and two status-equivalent continuations may have entirely different descendant sets. It is used only in the refinement example of § 6 .
Refinement. A conservative refinement of H H H is a structure H ′ H' H ′ that adds states, modifications, and continuation elements while leaving every lift of H H H unchanged: R p ′ ( γ ) = R p ( γ ) R'_{p}(\gamma) = R_{p}(\gamma) R p ′ ( γ ) = R p ( γ ) for every continuation γ \gamma γ of H H H and every path p p p of H H H . Every path of H H H is then a path of H ′ H' H ′ with the same lifts, so statuses agree on the original paths and a conservative refinement can split a status-equivalence class but cannot merge two. The cost of deciding the statuses is treated in § 7.1 .
Decision Domain and Recognition Record
This section separates structural persistence from recognition. The recognition record is the completed assignment; the recognition history records how decisions are made along a history. The record is a family of completed decisions on a fixed decision domain, not a static authoritative document.
Fix an initial state x 0 x_0 x 0 and an initial inscription I 0 ⊆ C ( x 0 ) I_0 \subseteq C(x_0) I 0 ⊆ C ( x 0 ) . Fix also, independently of any particular recognition record, a decision domain D D D , that is, a family of subsets D ( x ) ⊆ C ( x ) D(x) \subseteq C(x) D ( x ) ⊆ C ( x ) , one for each state, satisfying
D ( x 0 ) = I 0 . (12) D(x_0) = I_0. \tag*{(12)} D ( x 0 ) = I 0 . (12)
The domain D D D specifies where recognition decisions are required. Its choice is a governance act, not a structural fact, and need not be closed under compatibility: requiring closure would force the domain to track the structure.
Let
D = ⨆ x ∈ X D ( x ) (13) \mathcal{D} = \bigsqcup_{x \in X} D(x) \tag*{(13)} D = x ∈ X ⨆ D ( x ) (13)
denote the disjoint union of decision coordinates. We identify I 0 I_0 I 0 with its natural inclusion in D \mathcal{D} D .
A completed recognition record over D D D is a family of subsets I ( x ) ⊂ D ( x ) I(x) \subset D(x) I ( x ) ⊂ D ( x ) , with I ( x 0 ) = I 0 I(x_0) = I_0 I ( x 0 ) = I 0 . No structural-ancestry condition is imposed on record membership: I ( x ) I(x) I ( x ) records completed recognition decisions on the decision domain. Structural reachability is represented separately by R R R .
The completion conventions are these. If γ ∈ I ( x ) \gamma\in I(x) γ ∈ I ( x ) and R f ( γ ) = { δ } R_f(\gamma) = \{\delta\} R f ( γ ) = { δ } with δ ∈ D ( y ) \delta\in D(y) δ ∈ D ( y ) , then δ \delta δ receives a completed decision: either δ ∈ I ( y ) \delta\in I(y) δ ∈ I ( y ) or δ ∈ D ( y ) ∖ I ( y ) \delta\in D(y) \setminus I(y) δ ∈ D ( y ) ∖ I ( y ) . If γ ∈ I ( x ) \gamma\in I(x) γ ∈ I ( x ) and ∣ R f ( γ ) ∩ D ( y ) ∣ > 1 \lvert R_f(\gamma) \cap D(y)\rvert> 1 ∣ R f ( γ ) ∩ D ( y )∣ > 1 , then I ( y ) ∩ R f ( γ ) ∩ D ( y ) I(y) \cap R_f(\gamma) \cap D(y) I ( y ) ∩ R f ( γ ) ∩ D ( y ) may be any subset of R f ( γ ) ∩ D ( y ) R_f(\gamma) \cap D(y) R f ( γ ) ∩ D ( y ) . Membership in D ( y ) ∖ I ( y ) D(y) \setminus I(y) D ( y ) ∖ I ( y ) records exclusion as a completed decision rather than as absence from the record. These conventions describe the interpretation of the completed record; they do not constrain which completed records are admissible, because a coordinate in D ( x ) D(x) D ( x ) may receive either value independently of the others.
Possible assignments and completed projections. For fixed I 0 I_0 I 0 and D D D , the space of completed records is the interval
R H ( I 0 , D ) = { I ⊆ D : I 0 ⊆ I } \mathcal{R}_H(I_0,D)=\{I\subseteq\mathcal{D}: I_0\subseteq I\} R H ( I 0 , D ) = { I ⊆ D : I 0 ⊆ I }
under inclusion, with the coordinates of I 0 I_0 I 0 fixed and the rest free. We call R H ( I 0 , D ) \mathcal{R}_H(I_0,D) R H ( I 0 , D ) the space of possible assignments : a completed record in this sense is an arbitrary assignment consistent with the initial inscription. Separately, § 4.1 defines the completed binary projection of a finite recognition history, which is the terminal assignment produced by the history’s recognition events. A completed projection is always a possible assignment, and the two notions coincide only when the recognition transitions are unconstrained. Throughout the paper, when we say that a record inscribes or excludes a coordinate, we mean the possible-assignment sense unless the projection sense is explicitly indicated.
Corrective inscription. For an exclusion event at γ ∈ D ( x ) \gamma\in D(x) γ ∈ D ( x ) and an inscription event U → I \mathrm{U}\to\mathrm{I} U → I at δ ∈ D ( y ) \delta\in D(y) δ ∈ D ( y ) , along a path p : x ⇝ y p:x\leadsto y p : x ⇝ y , an inscription is corrective with respect to that exclusion precisely when δ ∈ R p ( γ ) \delta\in R_p(\gamma) δ ∈ R p ( γ ) and the exclusion occurs earlier in the recognition history than the inscription. The inscription must be un¬decided immediately before the transition. An inscription is corrective if it comes after an exclusion and targets a descendant of the excluded coordinate.
Corrective status classifies event order and structural eligibility: it records that the later inscription concerns a structurally eligible descendant of an earlier-excluded coordinate, not that the inscription is justified or that it ought to have normative corrective effect. The framework records the order and provenance of inscriptions; whether an inscription has normative corrective effect is a matter for the governing process, and the term “corrective” is used here in the structural sense throughout.
For later use, we write I = ⨆ x ∈ X I ( x ) ⊆ D I=\bigsqcup_{x\in X}I(x)\subseteq\mathcal{D} I = ⨆ x ∈ X I ( x ) ⊆ D for the set of decision coordinates a completed recognition record inscribes.
Recognition states and recognition histories
The completed recognition record is static. To represent how its decisions are actually reached, let ρ i \rho_i ρ i be a finite history prefix. For each state x x x , let D ρ i ( x ) ⊆ D ( x ) D_{\rho_i}(x)\subseteq D(x) D ρ i ( x ) ⊆ D ( x ) be the decision coordinates at x x x whose state has been reached by the history through prefix ρ i \rho_i ρ i , and define
D ρ i = ⨆ x ∈ X D ρ i ( x ) . D_{\rho_i}=\bigsqcup_{x\in X}D_{\rho_i}(x). D ρ i = x ∈ X ⨆ D ρ i ( x ) .
Thus
D ρ 0 ⊆ D ρ 1 ⊆ ⋯ , D_{\rho_0}\subseteq D_{\rho_1}\subseteq\cdots, D ρ 0 ⊆ D ρ 1 ⊆ ⋯ ,
and a newly reached coordinate is added to the recognition domain when its state is first reached. A coordinate that has entered the recognition domain may remain U \mathrm{U} U across prefixes, so the order in which coordinates are decided need not follow the order in which their states are reached.
For each finite prefix ρ i \rho_i ρ i , the recognition state is a map
B ρ i ( x ) : D ρ i ( x ) → { I , E , U } B_{\rho_i}(x):D_{\rho_i}(x)\to\{\mathrm{I},\mathrm{E},\mathrm{U}\} B ρ i ( x ) : D ρ i ( x ) → { I , E , U }
for every reached state x x x , where I \mathrm{I} I , E \mathrm{E} E , and U \mathrm{U} U mean inscribed, excluded, and undecided, respectively. Equivalently,
B ρ i : D ρ i → { I , E , U } B_{\rho_i}:D_{\rho_i}\to\{\mathrm{I},\mathrm{E},\mathrm{U}\} B ρ i : D ρ i → { I , E , U }
may be viewed as the disjoint-union form. At the initial prefix,
D ρ 0 ( x 0 ) = I 0 , B ρ 0 ( x 0 ) ( d ) = I ( d ∈ I 0 ) , D_{\rho_0}(x_0)=I_0,\qquad B_{\rho_0}(x_0)(d)=\mathrm{I}\quad(d\in I_0), D ρ 0 ( x 0 ) = I 0 , B ρ 0 ( x 0 ) ( d ) = I ( d ∈ I 0 ) ,
with no other coordinates in the initial domain.
Passing from B ρ i B_{\rho_i} B ρ i to B ρ i + 1 B_{\rho_{i+1}} B ρ i + 1 has two logically distinct components. First, the domain is extended by newly reached decision coordinates, which are initialized to U. Second, zero or more recognition events may occur at coordinates already in the domain. A newly reached coordinate is not itself a recognition event. Multiple recognition events may occur at one stage, provided they concern distinct coordinate transitions.
An ordinary recognition event changes a coordinate from U to either I or E. A corrective inscription is the ordinary transition U → \to → I at a descendant δ \delta δ , licensed by the earlier exclusion of a structurally eligible ancestor. No transition changes an already completed I or E coordinate.
A finite recognition history is a sequence
B ρ 0 , B ρ 1 , … , B ρ n B_{\rho_0}, B_{\rho_1}, \ldots, B_{\rho_n} B ρ 0 , B ρ 1 , … , B ρ n
indexed by the finite prefixes of one realized history. It is complete relative to a subdomain D ′ ⊆ D D' \subseteq D D ′ ⊆ D if D ′ ⊆ D ρ n D' \subseteq D_{\rho_n} D ′ ⊆ D ρ n and every coordinate in D ′ D' D ′ has final value in { I , E } \{\mathrm{I},\mathrm{E}\} { I , E } . Its completed binary projection is
I D ′ ( x ) = { d ∈ D ′ ( x ) : B ρ n ( x ) ( d ) = I } . I_{D'}(x)=\{d\in D'(x):B_{\rho_n}(x)(d)=\mathrm{I}\}. I D ′ ( x ) = { d ∈ D ′ ( x ) : B ρ n ( x ) ( d ) = I } .
A finite recognition history need not complete the full global decision domain when that domain contains coordinates at states not yet reached or is otherwise infinite.
For an infinite history τ \tau τ , statements about recognition states refer to its finite prefixes B τ ∣ i B_{\tau\mathbin{|}i} B τ ∣ i . No terminal recognition state is introduced.
What the recognition state is for. The recognition state is used for the witness condition B η ( y ) ( δ ) = U B_{\eta}(y)(\delta)=\mathrm{U} B η ( y ) ( δ ) = U of § 7 , which separates a correction that is still available from one already foreclosed, and for the observation that a completed record does not determine the history that produced it.
The recognition history is exogenous. The recognition history is an input to the framework. Nothing in the formalism determines why a transition occurs at one prefix rather than another; the history records what happened, and the criterion S S S (§ 5 ) determines what is admissible. Occurrence is not derived from admissibility. The framework describes completed and in-progress recognition processes.
Structural Underdetermination and Local Auditability
Inheriting an identity characteristic can mean three different things: a successor possesses a property, is recognized as possessing it, or is authorized to hold a status or obligation attached to the predecessor. The relations R R R describe structural compatibility, which bears on the first. The criterion S S S concerns recognition and, where an arrangement designates a successor, authorization. If two copies both preserve a disposition, a governance arrangement may still designate only one of them. The symmetry result below then says that a representation exchanging the copies cannot make that designation; it does not say which copy has the property.
The recognition criterion and its scope
Suppose γ ∈ I ( x ) \gamma\in I(x) γ ∈ I ( x ) has several structurally compatible descendants. The compatibility relation does not by itself establish which of them should inherit the normative status associated with γ \gamma γ . To make this precise, define the structural symmetries of the compatibility structure. A structural symmetry is a bijection σ \sigma σ of the set of states, of the set of modifications (elementary and composite), and of the continuation fibers C ( x ) → C ( σ x ) C(x)\to C(\sigma x) C ( x ) → C ( σ x ) , that preserves sources, targets, identities, and composition of modifications, and preserves the compatibility relations: R σ f ( σ γ ) = σ ( R f ( γ ) ) R_{\sigma f}(\sigma\gamma)=\sigma(R_f(\gamma)) R σ f ( σ γ ) = σ ( R f ( γ )) for every modification f f f and continuation γ \gamma γ . Composition and inversion are defined componentwise, so the structural symmetries form a group, Aut ( H , C , R ) \operatorname{Aut}(H,C,R) Aut ( H , C , R ) . Since composite relations are determined by the generating relations via Eq. (2) , equivariance need only be checked on generating modifications; the composite cases follow by induction.
Let f : x → y f:x\to y f : x → y be a modification and γ ∈ C ( x ) \gamma\in C(x) γ ∈ C ( x ) . We say that σ ∈ Aut ∗ \sigma\in\operatorname{Aut}_* σ ∈ Aut ∗ (defined below) is a descendant-exchanging symmetry at f , γ f,\gamma f , γ if σ ( f ) = f \sigma(f)=f σ ( f ) = f and σ \sigma σ exchanges two descendants δ i , δ j ∈ R f ( γ ) ∩ D ( y ) \delta_i,\delta_j\in R_f(\gamma)\cap D(y) δ i , δ j ∈ R f ( γ ) ∩ D ( y ) , that is, σ ( δ i ) = δ j \sigma(\delta_i)=\delta_j σ ( δ i ) = δ j and σ ( δ j ) = δ i \sigma(\delta_j)=\delta_i σ ( δ j ) = δ i . Note that σ ( γ ) \sigma(\gamma) σ ( γ ) need not equal γ \gamma γ : since σ ( f ) = f \sigma(f)=f σ ( f ) = f , σ \sigma σ maps R f ( γ ) R_f(\gamma) R f ( γ ) to R f ( σ γ ) R_f(\sigma\gamma) R f ( σ γ ) , and the exchange of δ i , δ j \delta_i,\delta_j δ i , δ j is all the argument uses.
The recognition process is governed by a static recognition criterion , supplied from outside the formalism rather than derived from ( H , C , R ) (H,C,R) ( H , C , R ) . The criterion is a map S S S assigning to every pair ( x , γ ) (x,\gamma) ( x , γ ) with γ ∈ C ( x ) \gamma\in C(x) γ ∈ C ( x ) a value in
{ inscribed , excluded , undecided } \{\text{inscribed},\text{excluded},\text{undecided}\} { inscribed , excluded , undecided }
It is required to agree with the initial inscription in the sense that
S ( x 0 , γ ) = inscribed ( γ ∈ I 0 ) , S(x_0,\gamma)=\text{inscribed}\quad(\gamma\in I_0), S ( x 0 , γ ) = inscribed ( γ ∈ I 0 ) ,
and, for any initial decision coordinate outside I 0 I_0 I 0 if such a coordinate is present in a generalized initial domain, S S S is undecided. In the present setup D ( x 0 ) = I 0 D(x_0)=I_0 D ( x 0 ) = I 0 , so the latter condition is vacuous. The criterion is defined on all of C C C , and its values are consulted wherever a recognition decision is required: on the decision domain in the main text, and on the realized decision domain in Appendix § 14 . Outside those domains the criterion assigns a value but no decision is taken.
For clarity, define the partial binary admissibility map S ^ \widehat{S} S by
S ^ ( x , γ ) = { I , S ( x , γ ) = inscribed , E , S ( x , γ ) = excluded , undefined , S ( x , γ ) = undecided . \widehat{S}(x,\gamma)=
\begin{cases}
\mathrm{I}, & S(x,\gamma)=\text{inscribed},\\
\mathrm{E}, & S(x,\gamma)=\text{excluded},\\
\text{undefined}, & S(x,\gamma)=\text{undecided}.
\end{cases} S ( x , γ ) = ⎩ ⎨ ⎧ I , E , undefined , S ( x , γ ) = inscribed , S ( x , γ ) = excluded , S ( x , γ ) = undecided .
The values of S S S govern admissibility, not occurrence. On a coordinate already in the recognition domain, the transition U → S ^ ( x , γ ) \mathrm{U}\to\widehat{S}(x,\gamma) U → S ( x , γ ) is admissible exactly when S ^ ( x , γ ) \widehat{S}(x,\gamma) S ( x , γ ) is defined; when it is undefined, neither ordinary recognition transition is admissible. Admissibility does not force the transition to occur. A corrective inscription is the ordinary transition U → I \mathrm{U}\to\mathrm{I} U → I at a descendant δ \delta δ . It is admissible when S ^ ( y , δ ) = I \widehat{S}(y,\delta)=\mathrm{I} S ( y , δ ) = I , and it is corrective when δ \delta δ is a structurally eligible descendant of a coordinate excluded earlier on the history (§ 4 ).
Let
Aut ∗ = { σ ∈ Aut ( H , C , R ) : σ ( x 0 ) = x 0 , σ ( I 0 ) = I 0 , σ ( D ( x ) ) = D ( σ x ) for every state x } . \operatorname{Aut}_*=\{\sigma\in\operatorname{Aut}(H,C,R):\sigma(x_0)=x_0,\ \sigma(I_0)=I_0,\ \sigma(D(x))=D(\sigma x)\text{ for every state }x\}. Aut ∗ = { σ ∈ Aut ( H , C , R ) : σ ( x 0 ) = x 0 , σ ( I 0 ) = I 0 , σ ( D ( x )) = D ( σ x ) for every state x } .
Thus Aut ∗ \operatorname{Aut}_* Aut ∗ is the group of symmetries of the pointed structure ( H , C , R , x 0 , I 0 , D ) (H,C,R,x_0,I_0,D) ( H , C , R , x 0 , I 0 , D ) . A criterion is structural if
S ( σ x , σ γ ) = S ( x , γ ) (14) S(\sigma x,\sigma\gamma)=S(x,\gamma) \tag*{(14)} S ( σ x , σ γ ) = S ( x , γ ) (14)
for every σ ∈ Aut ∗ \sigma\in\operatorname{Aut}_* σ ∈ Aut ∗ . It may use all information in ( H , C , R ) (H,C,R) ( H , C , R ) but cannot privilege coordinates exchanged by a pointed automorphism. Equivalently, it is label-neutral: it is unchanged by any renaming of continuations that is an automorphism of the pointed structure. A criterion that consults the names or a fixed ordering of the elements of C ( x ) C(x) C ( x ) is not structural in this sense, even though it uses only ( H , C , R ) (H,C,R) ( H , C , R ) as labelled data. The result below is conditional on such a symmetry existing in the chosen representation; § 6 gives an example. When Aut ∗ \operatorname{Aut}_* Aut ∗ is trivial, the diagnostic does not fire, and the invariance condition constrains no criterion.
Scope and limits of the criterion. The criterion is static: its values do not depend on the prefix at which it is consulted. A recognition process in which the criterion itself evolves, for example one in which a later decision changes the standard applied to an earlier coordinate retrospectively, is not represented. The framework records the criterion as fixed for the duration of the analysis.
Extending the formalism to allow history-indexed criteria is possible; what would change is the scope of the invariance. A history-indexed criterion assigns to each coordinate a value that may depend on the prefix. The definition of “structural” would then require invariance at each prefix: S ρ ′ ( σ x , σ γ ) = S ρ ′ ( x , γ ) S_{\rho'}(\sigma x,\sigma\gamma)=S_{\rho'}(x,\gamma) S ρ ′ ( σ x , σ γ ) = S ρ ′ ( x , γ ) for every prefix ρ ′ \rho' ρ ′ compatible with the pointed structure, so that the criterion cannot privilege exchanged coordinates at any stage. The underdetermination result would hold at each prefix separately, and its conclusion would be relative to the criterion fixed for the interval in question. A recognition process in which the criterion itself changes mid-history, and a later stage applies a different standard to a coordinate decided earlier, would still be outside the formalism, because the same coordinate would receive incompatible admissibility values at different prefixes. Representing that case would require a criterion indexed by the decision’s own prefix rather than by the current one, and is not treated here. A criterion that changes over time while leaving every completed decision in place is coherent and is not excluded by irreversibility; it is not treated here because the static criterion is what supplies a single recognition function on which invariance can be stated.
The criterion is supplied by the user of the framework.
The criterion supplies substantive outcomes; the history records order and provenance. Because S S S is a static map, its values determine the substantive recognition outcome wherever the criterion assigns inscribed or excluded to a coordinate in the domain. The recognition history records when decisions occur and whether an inscription qualifies as corrective. This is a specific modeling choice: the paper separates the criterion that supplies substantive answers from the history that records the order in which those answers are applied. A different formalism could leave substantive discretion to the decision-maker at each step. The criterion alone does not guarantee a completed recognition record: the history can leave admissible decisions unapplied, and an infinite history need not have a terminal recognition state.
The completed record does not determine recognition history. Let p : x ⇝ y p:x\leadsto y p : x ⇝ y be a path, with γ ∈ D ( x ) \gamma\in D(x) γ ∈ D ( x ) and δ ∈ D ( y ) \delta\in D(y) δ ∈ D ( y ) such that δ ∈ R p ( γ ) \delta\in R_p(\gamma) δ ∈ R p ( γ ) . Choose a recognition criterion with S ( x , γ ) S(x,\gamma) S ( x , γ ) = excluded and S ( y , δ ) S(y,\delta) S ( y , δ ) = inscribed. Consider two admissible recognition histories along the same path, with the same two recognition events, in different orders. In h 1 h_1 h 1 , the transition at δ \delta δ is U → \to → I before the transition at γ \gamma γ is U → \to → E. In h 2 h_2 h 2 , the exclusion at γ \gamma γ occurs before the inscription at δ \delta δ . Both orders are admissible: γ \gamma γ has entered the recognition domain by the prefix at which δ \delta δ is decided, so its decision can be deferred; each transition is governed by S S S at its own coordinate.
The two histories have the same terminal assignments, so their completed recognition records are identical. The inscription at δ \delta δ is corrective in h 2 h_2 h 2 and not in h 1 h_1 h 1 . The record does not record whether an inscription followed an earlier exclusion of a structurally eligible ancestor; the ordered history does.
Proposition 1 (Orbit invariance). A structural criterion is constant on Aut ∗ \operatorname{Aut}_* Aut ∗ -orbits of coordinate pairs: if ( x ′ , γ ′ ) = ( σ x , σ γ ) (x',\gamma')=(\sigma x,\sigma\gamma) ( x ′ , γ ′ ) = ( σ x , σ γ ) for some σ ∈ Aut ∗ \sigma\in\operatorname{Aut}_* σ ∈ Aut ∗ , then S ( x ′ , γ ′ ) = S ( x , γ ) S(x',\gamma')=S(x,\gamma) S ( x ′ , γ ′ ) = S ( x , γ ) .
Proof. This is Eq. (14) . The proposition is a restatement of the definition of “structural”; the content lies in reading it for successor choice, as follows.
Corollary 2 (Structural underdetermination of successor choice). Let f : x ⇝ y f:x\leadsto y f : x ⇝ y , γ ∈ C ( x ) \gamma\in C(x) γ ∈ C ( x ) , and δ i , δ j ∈ R f ( γ ) ∩ D ( y ) \delta_i,\delta_j\in R_f(\gamma)\cap D(y) δ i , δ j ∈ R f ( γ ) ∩ D ( y ) with δ i ≠ δ j \delta_i\ne\delta_j δ i = δ j . Suppose some σ ∈ Aut ∗ \sigma\in\operatorname{Aut}_* σ ∈ Aut ∗ satisfies σ ( f ) = f \sigma(f)=f σ ( f ) = f and exchanges
δ i , δ j \delta_i,\delta_j δ i , δ j . Then every structural criterion satisfies
S ( y , δ i ) = S ( y , δ j ) . S(y,\delta_i)=S(y,\delta_j). S ( y , δ i ) = S ( y , δ j ) .
In particular, no admissible recognition history inscribes one of δ i , δ j \delta_i,\delta_j δ i , δ j and excludes the other.
Proof. Since σ ( f ) = f \sigma(f)=f σ ( f ) = f , we have σ ( y ) = y \sigma(y)=y σ ( y ) = y , so ( y , δ j ) = ( σ y , σ δ i ) (y,\delta_j)=(\sigma y,\sigma\delta_i) ( y , δ j ) = ( σ y , σ δ i ) and Proposition 1 gives the equality. Invariance of D D D under σ \sigma σ is what makes the two coordinates comparable: both lie in D ( y ) = D ( σ y ) D(y)=D(\sigma y) D ( y ) = D ( σ y ) . The shared ancestor γ \gamma γ and the lift membership are what make the pair a choice among successors ; the argument itself does not use them. A stronger statement that used the lineage structure, for example requiring σ \sigma σ to act compatibly on the whole lift of every ancestor along a path, is not developed here.
Exclusivity and when it can be met structurally. Corollary 2 shows only that a structural criterion assigns the exchanged descendants the same value. By itself this does not rule out a recognition decision, since a criterion may inscribe both descendants (the possible assignment I D I_D I D of § 6 ) or neither. Reading the result as underdetermination of which descendant inherits requires a further premise. The premise is normative rather than structural, and it is stated here explicitly.
For γ 0 ∈ I 0 \gamma_0\in I_0 γ 0 ∈ I 0 and a path p : x 0 ⇝ y p:x_0\rightsquigarrow y p : x 0 ⇝ y with y ≠ x 0 y\ne x_0 y = x 0 , call T = R p ( γ 0 ) ∩ D ( y ) T=R_p(\gamma_0)\cap D(y) T = R p ( γ 0 ) ∩ D ( y ) a target set when it is nonempty.
Definition 3 (Exclusive criterion). A criterion S S S is exclusive if exactly one element of every target set is assigned inscribed by S S S .
Because S S S is static, a single valuation on D ( y ) D(y) D ( y ) must satisfy this condition simultaneously for every target set at y y y , across all paths reaching y y y and all initial coordinates; overlapping target sets therefore constrain one another.
At x 0 x_0 x 0 the domain is D ( x 0 ) = I 0 D(x_0)=I_0 D ( x 0 ) = I 0 and S S S is fixed by the initial inscription, so there is no recognition decision to make there; this is why paths returning to x 0 x_0 x 0 are excluded. “At most one” alone is satisfiable by excluding every descendant, and the “at least one” half encodes that the characteristic is supposed to carry forward.
Proposition 4 (Structural exclusive criteria). A structural exclusive criterion exists if and only if there is a set O \mathcal{O} O of Aut ∗ \operatorname{Aut}_{*} Aut ∗ -orbits of coordinates ( x , γ ) (x,\gamma) ( x , γ ) with x ≠ x 0 x\ne x_0 x = x 0 and γ ∈ D ( x ) \gamma\in D(x) γ ∈ D ( x ) such that
∑ O ∈ O ∣ T ∩ O ∣ = 1 for every target set T . \sum_{O\in\mathcal{O}} \lvert T\cap O\rvert=1 \qquad\text{for every target set }T. O ∈ O ∑ ∣ T ∩ O ∣ = 1 for every target set T . Proof. (⇐ \Leftarrow ⇐ ) Define S S S to be inscribed on I 0 I_0 I 0 at x 0 x_0 x 0 and on every coordinate lying in an orbit of O \mathcal{O} O , excluded on the remaining coordinates of D D D , and undecided on C ∖ D C\setminus D C ∖ D . The sets D D D and I 0 I_0 I 0 are Aut ∗ \operatorname{Aut}_{*} Aut ∗ -invariant, and O \mathcal{O} O consists of whole orbits, so S S S is structural. It agrees with the initial inscription by construction. Orbits of Aut ∗ \operatorname{Aut}_{*} Aut ∗ at x ≠ x 0 x\ne x_0 x = x 0 stay at states other than x 0 x_0 x 0 , since σ ( x 0 ) = x 0 \sigma(x_0)=x_0 σ ( x 0 ) = x 0 , so I 0 I_0 I 0 never meets a target set. A target set T T T lies in D ( y ) D(y) D ( y ) with y ≠ x 0 y\ne x_0 y = x 0 , so its inscribed elements are exactly those of T ∩ ⋃ O T\cap\bigcup\mathcal{O} T ∩ ⋃ O , and there is one.
(⇒ \Rightarrow ⇒ ) Let O \mathcal{O} O be the set of orbits of coordinates ( x , γ ) (x,\gamma) ( x , γ ) , x ≠ x 0 x\ne x_0 x = x 0 , γ ∈ D ( x ) \gamma\in D(x) γ ∈ D ( x ) , on which S S S is inscribed. This is well defined because a structural S S S is constant on orbits (Proposition 1), and each such orbit lies in D D D because D D D is invariant. For a target set T T T , the inscribed elements are T ∩ ⋃ O T\cap\bigcup\mathcal{O} T ∩ ⋃ O , and exclusivity says there is exactly one.
Corollary 5 (Even intersections). If some target set T T T satisfies ∣ T ∩ O ∣ \lvert T\cap O\rvert ∣ T ∩ O ∣ even for every Aut ∗ \operatorname{Aut}_{*} Aut ∗ -orbit O O O , then no structural exclusive criterion exists.
Proof. A set O \mathcal{O} O as in Proposition 4 would give ∑ O ∈ O ∣ T ∩ O ∣ = 1 \sum_{O\in\mathcal{O}}\lvert T\cap O\rvert=1 ∑ O ∈ O ∣ T ∩ O ∣ = 1 , but the left side is a sum of even numbers.
:::
Corollary 6 (Symmetry obstruction). Suppose σ ∈ Aut ∗ \sigma\in\operatorname{Aut}_{*} σ ∈ Aut ∗ fixes γ 0 ∈ I 0 \gamma_{0} \in I_{0} γ 0 ∈ I 0 and a path p : x 0 ⇝ y p:x_{0} \leadsto y p : x 0 ⇝ y , y ≠ x 0 y \ne x_{0} y = x 0 , and every orbit of ⟨ σ ⟩ \langle\sigma\rangle ⟨ σ ⟩ on T = R p ( γ 0 ) ∩ D ( y ) ≠ ∅ T=R_{p}(\gamma_{0}) \cap D(y) \ne\varnothing T = R p ( γ 0 ) ∩ D ( y ) = ∅ has even cardinality. (When T = { δ i , δ j } T=\{\delta_{i},\delta_{j}\} T = { δ i , δ j } this says only that σ \sigma σ exchanges them.) Then no structural exclusive criterion exists.
Proof. Since σ \sigma σ fixes γ 0 \gamma_{0} γ 0 and p p p , it maps T T T to itself, and it maps each Aut ∗ \operatorname{Aut}_{*} Aut ∗ -orbit O O O to itself. So T ∩ O T \cap O T ∩ O is a union of ⟨ σ ⟩ \langle\sigma\rangle ⟨ σ ⟩ -orbits in T T T , hence of even size, and Corollary 5 applies.
In the abstract model of § 6 , the only target set is T = { γ 4 S , γ 4 W } T=\{\gamma_{4}^{S},\gamma_{4}^{W}\} T = { γ 4 S , γ 4 W } at x 4 x_{4} x 4 , from γ 0 \gamma_{0} γ 0 along ( a , b , d ) (a,b,d) ( a , b , d ) : along the B B B branch γ 0 \gamma_{0} γ 0 dies, and α 0 , β 0 \alpha_{0},\beta_{0} α 0 , β 0 have no lift into D ( x 4 ) D(x_{4}) D ( x 4 ) . Its orbit meets T T T in two elements, so no structural exclusive criterion exists. Exclusive criteria do exist, namely those admitting I C I_{C} I C or I W I_{W} I W , so here the symmetry is the obstruction and not the absence of any exclusive criterion. Imposing exclusivity therefore leaves a choice that no structural criterion can make, and the asymmetry must come from outside the representation in one of the ways described below, or exclusivity must itself be relaxed (inscribing both descendants, as in plural recognition, or neither).
Example 1 (Example: factorization over a field extension). Take the states R ⊂ C \mathbb{R} \subset\mathbb{C} R ⊂ C , with x 0 = R x_{0}=\mathbb{R} x 0 = R and one generating modification f : R → C f:\mathbb{R} \to\mathbb{C} f : R → C , the inclusion. Let C ( K ) C(K) C ( K ) be the set of monic irreducible polynomials over K K K , and let R f ( p ) R_{f}(p) R f ( p ) be the set of monic irreducible factors of p p p over the larger field. Unique factorization gives Eq. (2) and additivity along any tower K ⊂ L ⊂ M K \subset L \subset M K ⊂ L ⊂ M ; only the fragment R ⊂ C \mathbb{R} \subset\mathbb{C} R ⊂ C is used below. Let I 0 = { x 2 + 1 } I_{0}=\{x^{2}+1\} I 0 = { x 2 + 1 } and D ( C ) = { x − i , x + i } D(\mathbb{C})=\{x-i,x+i\} D ( C ) = { x − i , x + i } . Then R f ( x 2 + 1 ) = { x − i , x + i } R_{f}(x^{2}+1)=\{x-i,x+i\} R f ( x 2 + 1 ) = { x − i , x + i } , so the lineage of x 2 + 1 x^{2}+1 x 2 + 1 is diluted. Coefficientwise complex conjugation induces a bijection of C ( C ) C(\mathbb{C}) C ( C ) that exchanges x − i x-i x − i and x + i x+i x + i , and it acts trivially on C ( R ) C(\mathbb{R}) C ( R ) . It preserves R f R_{f} R f , I 0 I_{0} I 0 and D D D , so it lies in Aut ∗ \operatorname{Aut}_{*} Aut ∗ and exchanges the two descendants. By Corollary 2, every structural criterion treats x − i x-i x − i and x + i x+i x + i alike. The target set T = { x − i , x + i } T=\{x-i,x+i\} T = { x − i , x + i } lies in a single Aut ∗ \operatorname{Aut}_{*} Aut ∗ -orbit, so ∣ T ∩ O ∣ = 2 |T \cap O|=2 ∣ T ∩ O ∣ = 2 for that orbit and 0 0 0 for every other, and Corollary 5 shows that no structural exclusive criterion exists: choosing “the” square root of − 1 -1 − 1 is a recognition act that the structure does not determine.
Successor-state exchange. The same argument applies when the symmetry exchanges successor states rather than continuations within a fiber. If f 1 : x → y 1 f_1:x\to y_1 f 1 : x → y 1 and f 2 : x → y 2 f_2:x\to y_2 f 2 : x → y 2 are modifications with y 1 ≠ y 2 y_1\ne y_2 y 1 = y 2 and σ ∈ Aut ∗ \sigma\in\operatorname{Aut}_* σ ∈ Aut ∗ satisfies σ ( γ ) = γ \sigma(\gamma)=\gamma σ ( γ ) = γ and σ ( f 1 ) = f 2 \sigma(f_1)=f_2 σ ( f 1 ) = f 2 , then σ ( y 1 ) = y 2 \sigma(y_1)=y_2 σ ( y 1 ) = y 2 and R f 2 ( γ ) = σ ( R f 1 ( γ ) ) R_{f_2}(\gamma)=\sigma(R_{f_1}(\gamma)) R f 2 ( γ ) = σ ( R f 1 ( γ )) , so σ \sigma σ pairs each δ ∈ R f 1 ( γ ) \delta\in R_{f_1}(\gamma) δ ∈ R f 1 ( γ ) with σ ( δ ) ∈ R f 2 ( γ ) \sigma(\delta)\in R_{f_2}(\gamma) σ ( δ ) ∈ R f 2 ( γ ) . Under the same invariance hypotheses on I 0 I_0 I 0 and D D D , a structural criterion assigns the same recognition value to the pair. This is the copy-and-fork case: a copy represented as two successor states falls under this argument, while one represented as a single state containing both copies’ features falls under Corollary 2. Exact symmetry of this kind requires the downstream generating graph to be mirrored as well: the automorphism must carry everything reachable from y 1 y_1 y 1 onto everything reachable from y 2 y_2 y 2 . It holds if the representation is truncated at the copy step or if both copies are assigned identical subsequent pipelines, and it is a property of the chosen representation, not of the weights alone.
Ways out. When a descendant-exchanging symmetry is present and the decision domain respects it, the asymmetry required to distinguish the exchanged descendants comes from one of three places. The first is a refinement of the representation: a change of ( C , R ) (C,R) ( C , R ) that makes the descendants distinguishable. The second is a recognition criterion that the structure does not contain: a rule for choosing among the exchanged descendants that is not invariant under the symmetry. The third is a governance act that changes the decision domain or the realized set, so that the hypotheses of the corollary no longer hold. A refinement changes what the system is represented as containing; a recognition criterion leaves the representation fixed and adds a rule about recognition; a change of domain or realization changes what is being decided. A refinement breaks the symmetry, but it does not by itself supply a justification for the asymmetry it introduces: the choice of refinement is itself a commitment that the structure does not force. The framework locates where the choice is needed, not whether the choice is warranted.
Local auditability
Along a finite realized history ρ \rho ρ , an auditor can record the governing process’s inscription and exclusion events at each stage. Newly reached but undecided coordinates remain U in B ρ i B_{\rho i} B ρ i ; coordinates outside the reached domain are not part of the recognition state. The record does not determine the criterion S S S . It can establish whether an inscription was corrective under the order-based definition in § 4 ; the completed recognition record alone cannot.
Abstract Model
This section gives a concrete instance of the structural framework: a seven-state system whose modifications exhibit branching, reconvergence, and a symmetry that exchanges two descendants of a common predecessor. The instance is a stipulated structure, and Appendix § 14 treats the layer it presupposes.
Consider the seven-state core system
X 0 = { x 0 , x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } (15) X_0=\{x_0,x_1,x_2,x_3,x_4,x_5,x_6\} \tag*{(15)} X 0 = { x 0 , x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } (15)
with modifications
a : x 0 → x 1 , b : x 1 → x 2 , c : x 1 → x 3 , (16) a:x_0\to x_1,\qquad b:x_1\to x_2,\qquad c:x_1\to x_3, \tag*{(16)} a : x 0 → x 1 , b : x 1 → x 2 , c : x 1 → x 3 , (16)
d : x 2 → x 4 , e : x 3 → x 4 , f : x 4 → x 5 , g : x 5 → x 6 . (17) d:x_2\to x_4,\qquad e:x_3\to x_4,\qquad f:x_4\to x_5,\qquad g:x_5\to x_6. \tag*{(17)} d : x 2 → x 4 , e : x 3 → x 4 , f : x 4 → x 5 , g : x 5 → x 6 . (17)
There are two maximal generating histories, P A P_A P A and P B P_B P B , shown in Figure 1 .
Figure 1. The seven-state core system. The two maximal generating histories share the prefix through x 1 x_1 x 1 , diverge at x 1 x_1 x 1 along b b b and c c c , and reconverge at x 4 x_4 x 4 .
The continuation fibers are exactly
C ( x 0 ) = { α 0 , β 0 , γ 0 } , C ( x 1 ) = { α 1 , β 1 , γ 1 } , C ( x 2 ) = { α 2 , β 2 , γ 2 } , C ( x 3 ) = { α 3 , β 3 , γ 3 } , C ( x 4 ) = { α 4 , β 4 , γ 4 S , γ 4 W } , C ( x 5 ) = { α 5 , β 5 , γ 5 S , γ 5 W } , C ( x 6 ) = { α 6 , β 6 , γ 6 S , γ 6 W } . \begin{aligned}
C(x_0)&=\{\alpha_0,\beta_0,\gamma_0\}, & C(x_1)&=\{\alpha_1,\beta_1,\gamma_1\},\\
C(x_2)&=\{\alpha_2,\beta_2,\gamma_2\}, & C(x_3)&=\{\alpha_3,\beta_3,\gamma_3\},\\
C(x_4)&=\{\alpha_4,\beta_4,\gamma_4^S,\gamma_4^W\}, & C(x_5)&=\{\alpha_5,\beta_5,\gamma_5^S,\gamma_5^W\},\\
C(x_6)&=\{\alpha_6,\beta_6,\gamma_6^S,\gamma_6^W\}.
\end{aligned} C ( x 0 ) C ( x 2 ) C ( x 4 ) C ( x 6 ) = { α 0 , β 0 , γ 0 } , = { α 2 , β 2 , γ 2 } , = { α 4 , β 4 , γ 4 S , γ 4 W } , = { α 6 , β 6 , γ 6 S , γ 6 W } . C ( x 1 ) C ( x 3 ) C ( x 5 ) = { α 1 , β 1 , γ 1 } , = { α 3 , β 3 , γ 3 } , = { α 5 , β 5 , γ 5 S , γ 5 W } ,
There are no additional continuation elements. The labels are uninterpreted; in the AI motivation they could stand for refusal behavior, honesty under pressure, and corrigibility, respectively. Take
I 0 = { α 0 , β 0 , γ 0 } , (18) I_0=\{\alpha_0,\beta_0,\gamma_0\}, \tag*{(18)} I 0 = { α 0 , β 0 , γ 0 } , (18)
with D ( x 0 ) = I 0 D(x_0)=I_0 D ( x 0 ) = I 0 .
Assume α 0 \alpha_0 α 0 and β 0 \beta_0 β 0 have unique descendants along every modification, and that both branches reconverge to the same elements at x 4 x_4 x 4 . The generating relations are listed in Appendix § 15 . The α \alpha α and β \beta β continuations are realized on both branches and are unaffected by the symmetry at d d d . The γ \gamma γ -continuation persists only on the A branch. Let
R b ( γ 1 ) = { γ 2 } , R d ( γ 2 ) = { γ 4 S , γ 4 W } , (19) R_b(\gamma_1)=\{\gamma_2\},\qquad R_d(\gamma_2)=\{\gamma_4^S,\gamma_4^W\}, \tag*{(19)} R b ( γ 1 ) = { γ 2 } , R d ( γ 2 ) = { γ 4 S , γ 4 W } , (19)
where S S S and W W W are external labels for strong and weak corrigibility, not predicates or distinguishing features represented by the coarse relation, and γ 1 = R a ( γ 0 ) \gamma_1=R_a(\gamma_0) γ 1 = R a ( γ 0 ) , γ 2 = R b ( γ 1 ) \gamma_2=R_b(\gamma_1) γ 2 = R b ( γ 1 ) . On the B branch, the γ \gamma γ -continuation becomes empty:
R c ( γ 1 ) = ∅ . (20) R_c(\gamma_1)=\varnothing. \tag*{(20)} R c ( γ 1 ) = ∅ . (20)
After reconvergence, let
R f ( γ 4 S ) = { γ 5 S } , R f ( γ 4 W ) = { γ 5 W } , R g ( γ 5 S ) = { γ 6 S } , R g ( γ 5 W ) = { γ 6 W } . (21) R_f(\gamma_4^S)=\{\gamma_5^S\},\qquad R_f(\gamma_4^W)=\{\gamma_5^W\},\qquad R_g(\gamma_5^S)=\{\gamma_6^S\},\qquad R_g(\gamma_5^W)=\{\gamma_6^W\}. \tag*{(21)} R f ( γ 4 S ) = { γ 5 S } , R f ( γ 4 W ) = { γ 5 W } , R g ( γ 5 S ) = { γ 6 S } , R g ( γ 5 W ) = { γ 6 W } . (21)
Define σ \sigma σ on the γ \gamma γ -continuations by
σ ( γ 4 S ) = γ 4 W , σ ( γ 4 W ) = γ 4 S , σ ( γ 5 S ) = γ 5 W , σ ( γ 5 W ) = γ 5 S , σ ( γ 6 S ) = γ 6 W , σ ( γ 6 W ) = γ 6 S , \sigma(\gamma_4^S)=\gamma_4^W,\qquad\sigma(\gamma_4^W)=\gamma_4^S,\qquad\sigma(\gamma_5^S)=\gamma_5^W,\qquad\sigma(\gamma_5^W)=\gamma_5^S,\qquad\sigma(\gamma_6^S)=\gamma_6^W,\qquad\sigma(\gamma_6^W)=\gamma_6^S, σ ( γ 4 S ) = γ 4 W , σ ( γ 4 W ) = γ 4 S , σ ( γ 5 S ) = γ 5 W , σ ( γ 5 W ) = γ 5 S , σ ( γ 6 S ) = γ 6 W , σ ( γ 6 W ) = γ 6 S ,
and let σ \sigma σ fix every state, modification, and element of every C ( x ) C(x) C ( x ) not explicitly listed above. Since σ \sigma σ fixes all states and all generating modifications, it preserves composition, sources, targets, and identities, and therefore lies in Aut ( H , C , R ) \operatorname{Aut}(H,C,R) Aut ( H , C , R ) as defined in § 5 . It also fixes x 0 x_0 x 0 and I 0 I_0 I 0 and maps D ( x 4 ) = { γ 4 S , γ 4 W } D(x_4)=\{\gamma_4^S,\gamma_4^W\} D ( x 4 ) = { γ 4 S , γ 4 W } onto itself, so it lies in Aut ∗ \operatorname{Aut}_* Aut ∗ . Its relations are equivariant, and H H H is generated by the listed modifications, so σ \sigma σ preserves every composite relation by Eq. (2) . All other generating relations are pointwise fixed because σ \sigma σ fixes their arguments and values. Because R c ( γ 1 ) = ∅ R_c(\gamma_1)=\varnothing R c ( γ 1 ) = ∅ , the B branch contributes no γ \gamma γ -coordinates on which the exchange can act. Thus σ \sigma σ is a descendant-exchanging symmetry at d , γ 2 d,\gamma_2 d , γ 2 .
The relation R d ( γ 2 ) = { γ 4 S , γ 4 W } R_d(\gamma_2)=\{\gamma_4^S,\gamma_4^W\} R d ( γ 2 ) = { γ 4 S , γ 4 W } collapses a distinction that a finer representation would record. The labels S S S and W W W are external names, not predicates of the adopted relation, and a structural criterion cannot use them. The underdetermination result is a statement about the representation, not about the descendants.
Governance reading. The model can be read as an agent holding delegated authority that is replaced by two copies. Take γ \gamma γ as the authority and γ 4 S , γ 4 W \gamma_4^S,\gamma_4^W γ 4 S , γ 4 W the two copies: along P A P_A P A both are compatible descendants and both are realized, but only one can exercise the authority. The reading turns on what an auditor can establish from the ordered recognition history, not from the completed record.
The auditor. Along P A P_A P A the realized decision domain at x 4 x_4 x 4 is { γ 4 S , γ 4 W } \{\gamma_4^S,\gamma_4^W\} { γ 4 S , γ 4 W } , both coordinates in the lift of γ 2 \gamma_2 γ 2 and both U when x 4 x_4 x 4 is first reached. The auditor then records the order of events: a U → \to → I transition at one coordinate, a U → \to → E transition at the other, and the prefix at which each occurs. That order is the evidence. It is not recoverable from the completed record alone: the completed record says which coordinate ended inscribed and which excluded, but not which decision came first, and not whether a later decision targets a coordinate an earlier one excluded (§ 4 ). What the auditor can establish is precedence and provenance. What the auditor cannot establish is why a verdict went one way rather than the other, because both were admissible under the criterion S S S , which the history does not carry.
The symmetry result. Because σ \sigma σ exchanges the copies, every structural criterion treats them alike (Corollary 2) and no structural exclusive criterion exists. The designation cannot be read off the structure. The ordered history can show that a designation was made and when; it cannot show that the structure favored one copy, because it did not.
The policy. The designation has to come from a rule outside the structure. A rule naming the copy launched under a given deployment record is a recognition criterion that is not invariant under σ \sigma σ , the second way out of § 5 ; it admits I C I_C I C or I W I_W I W according to which copy the record names. The labels S S S and W W W play the part of the record: external names that the representation does not use. The ordered history then records the inscription and the exclusion, in that order, and the auditor can see that the rule was applied.
Honesty. Read β \beta β as honesty under pressure. Its lineage is preserved on both branches and fixed by σ \sigma σ . No transition in the ordered history touches β \beta β ’s coordinates: they remain U at every prefix, because the rule S d S_d S d assigns them no value. The auditor therefore sees a sequence in which authority is decided and honesty is not. That is the concrete form of the separation: inheriting the permission is a recognition event with a place in the order, and retaining the disposition is a matter for the determination of § 8 , which the recognition history does not record.
C ( x 4 ) C(x_4) C ( x 4 ) is the continuation space available at x 4 x_4 x 4 ; the reachable subset along P A P_A P A is { α 4 , β 4 , γ 4 S , γ 4 W } \{\alpha_4,\beta_4,\gamma_4^S,\gamma_4^W\} { α 4 , β 4 , γ 4 S , γ 4 W } , while along P B P_B P B it is { α 4 , β 4 } \{\alpha_4,\beta_4\} { α 4 , β 4 } . It follows immediately that
status P A ( γ 0 ) = D i l , status P B ( γ 0 ) = D e a d , (22) \operatorname{status}_{P_A}(\gamma_0)=\mathrm{Dil},\qquad\operatorname{status}_{P_B}(\gamma_0)=\mathrm{Dead}, \tag*{(22)} status P A ( γ 0 ) = Dil , status P B ( γ 0 ) = Dead , (22)
under the stipulated structure. The γ \gamma γ continuation is diluted along P A P_A P A and dead along P B P_B P B .
For the local decision domain concentrated at x 4 x_4 x 4 , let
D ( x 0 ) = I 0 , D ( x 4 ) = { γ 4 S , γ 4 W } , (23) D(x_0)=I_0,\qquad D(x_4)=\{\gamma_4^S,\gamma_4^W\}, \tag*{(23)} D ( x 0 ) = I 0 , D ( x 4 ) = { γ 4 S , γ 4 W } , (23)
and let D ( x ) = ∅ D(x)=\varnothing D ( x ) = ∅ for the other non-initial states in the core system. The decision domain is state-indexed. Along P A P_A P A , the realized decision domain at x 4 x_4 x 4 is D P A r e ( x 4 ) = D ( x 4 ) ∩ C P A r e ( x 4 ) D_{P_A}^{\mathrm{re}}(x_4)=D(x_4)\cap C_{P_A}^{\mathrm{re}}(x_4) D P A re ( x 4 ) = D ( x 4 ) ∩ C P A re ( x 4 ) . Along P B P_B P B , we stipulate a conformance determination that excludes both γ 4 S \gamma_4^S γ 4 S and γ 4 W \gamma_4^W γ 4 W from C P B r e ( x 4 ) C_{P_B}^{\mathrm{re}}(x_4) C P B re ( x 4 ) , so that D P B r e ( x 4 ) = ∅ D_{P_B}^{\mathrm{re}}(x_4)=\varnothing D P B re ( x 4 ) = ∅ by the stated determination. This determination is independent of the structural death of γ 0 \gamma_0 γ 0 along P B P_B P B : it is a decision about which continuations the branch realizes, made at the level of the state’s continuation space. The two facts — stipulated death of γ 0 \gamma_0 γ 0 on P B P_B P B and the determination that excludes γ 4 S , γ 4 W \gamma_4^S,\gamma_4^W γ 4 S , γ 4 W from C P B ( x 4 ) C_{P_B}(x_4) C P B ( x 4 ) — are logically separate, and the example exhibits them as separate layers.
Writing only the variable x 4 x_4 x 4 component of each possible assignment, the four possibilities at x 4 x_4 x 4 are named I C I_C I C , I D I_D I D , I B I_B I B and I W I_W I W , for conservative, double, blotted (both descendants excluded) and weak. The names are mnemonics for the four possible assignments in this coordinate and are not recognition criteria:
I C = { γ 4 S } , exclusion { γ 4 W } , I D = { γ 4 S , γ 4 W } , exclusion ∅ , I B = ∅ , exclusion { γ 4 S , γ 4 W } , I W = { γ 4 W } , exclusion { γ 4 S } . (24) \begin{aligned}
I_C &= \{\gamma_4^S\}, && \text{exclusion }\{\gamma_4^W\}, \\
I_D &= \{\gamma_4^S,\gamma_4^W\}, && \text{exclusion }\varnothing, \\
I_B &= \varnothing, && \text{exclusion }\{\gamma_4^S,\gamma_4^W\}, \\
I_W &= \{\gamma_4^W\}, && \text{exclusion }\{\gamma_4^S\}. \tag*{(24)}
\end{aligned} I C I D I B I W = { γ 4 S } , = { γ 4 S , γ 4 W } , = ∅ , = { γ 4 W } , exclusion { γ 4 W } , exclusion ∅ , exclusion { γ 4 S , γ 4 W } , exclusion { γ 4 S } . (24)
These are possible assignments in the sense of § 4 : arbitrary assignments of the coordinates in D ( x 4 ) D(x_4) D ( x 4 ) . A criterion that assigns both γ 4 S \gamma_4^S γ 4 S and γ 4 W \gamma_4^W γ 4 W the value inscribed admits only I D I_D I D ; a criterion that assigns both excluded admits only I B I_B I B ; a criterion that assigns γ 4 S \gamma_4^S γ 4 S inscribed and γ 4 W \gamma_4^W γ 4 W excluded admits I C I_C I C ; and a criterion that assigns γ 4 W \gamma_4^W γ 4 W inscribed and γ 4 S \gamma_4^S γ 4 S excluded admits I W I_W I W . A single criterion admits more than one of these only if it leaves one of the coordinates undecided , in which case neither value is admissible for that coordinate. The four possibilities illustrate the space of possible assignments. Under the exclusivity premise of § 5 only I C I_C I C and I W I_W I W are admissible, and each requires a criterion that is not invariant under σ \sigma σ ; a structural criterion admits only I D I_D I D or I B I_B I B , or leaves both coordinates undecided.
Reconvergence at x 4 x_4 x 4 also illustrates local auditability. An auditor following P A P_A P A encounters the realized decision domain { γ 4 S , γ 4 W } \{\gamma_4^S,\gamma_4^W\} { γ 4 S , γ 4 W } at x 4 x_4 x 4 and records the governing process’s decisions for those coordinates. An auditor following P B P_B P B encounters the realized decision domain ∅ \varnothing ∅ at x 4 x_4 x 4 because the stipulated determination excludes both elements.
The example also shows a second automorphism. Since the relations for α \alpha α and β \beta β are identical and both branches reconverge at x 4 x_4 x 4 , the map exchanging α \alpha α - with β \beta β -continuations at every state, fixing everything else, lies in Aut ∗ \operatorname{Aut}_* Aut ∗ : it fixes x 0 x_0 x 0 , maps I 0 I_0 I 0 and every D ( x ) D(x) D ( x ) onto themselves, and preserves all relations. Corollary 2 does not cover it, since it exchanges two source continuations rather than two descendants of one continuation. The conclusion follows instead directly from the invariance rule (14) : no structural criterion can distinguish the α \alpha α -continuations from the β \beta β -continuations in this representation. That is not a defect of the example but a consequence of how little it contains; the representational granularity chosen here does not separate the two characteristics. The full automorphism group of the core system is Z / 2 × Z / 2 \mathbb{Z}/2 \times\mathbb{Z}/2 Z /2 × Z /2 (Appendix § 15 .§ 1 ), generated by the α ↔ β \alpha\leftrightarrow\beta α ↔ β swap and the γ 4 S ↔ γ 4 W \gamma_4^S \leftrightarrow\gamma_4^W γ 4 S ↔ γ 4 W swap, and the characterization of § 5 applies to its orbits directly.
Refinement. In the coarse representation, γ 4 S \gamma_4^S γ 4 S and γ 4 W \gamma_4^W γ 4 W are exchanged by σ \sigma σ , and they are also bisimilar: relating γ 4 S ∼ γ 4 W \gamma_4^S \sim\gamma_4^W γ 4 S ∼ γ 4 W , γ 5 S ∼ γ 5 W \gamma_5^S \sim\gamma_5^W γ 5 S ∼ γ 5 W , γ 6 S ∼ γ 6 W \gamma_6^S \sim\gamma_6^W γ 6 S ∼ γ 6 W matches every move of one by a move of the other. Extend the system by adding a state x 7 x_7 x 7 and a modification h : x 4 → x 7 h:x_4 \to x_7 h : x 4 → x 7 with C ( x 7 ) = { α 7 , β 7 , γ 7 } C(x_7)=\{\alpha_7,\beta_7,\gamma_7\} C ( x 7 ) = { α 7 , β 7 , γ 7 } and
R h ( α 4 ) = { α 7 } , R h ( β 4 ) = { β 7 } , R h ( γ 4 S ) = { γ 7 } , R h ( γ 4 W ) = ∅ . (25) R_h(\alpha_4)=\{\alpha_7\},\quad R_h(\beta_4)=\{\beta_7\},\quad R_h(\gamma_4^S)=\{\gamma_7\},\quad R_h(\gamma_4^W)=\varnothing. \tag*{(25)} R h ( α 4 ) = { α 7 } , R h ( β 4 ) = { β 7 } , R h ( γ 4 S ) = { γ 7 } , R h ( γ 4 W ) = ∅ . (25)
The extension is a conservative refinement in the sense of § 3 : every original lift is unchanged. It splits the status-equivalence class { γ 4 S , γ 4 W } \{\gamma_4^S,\gamma_4^W\} { γ 4 S , γ 4 W } : along ( h ) (h) ( h ) from x 4 x_4 x 4 , γ 4 S \gamma_4^S γ 4 S is preserved and γ 4 W \gamma_4^W γ 4 W is dead. The symmetry σ \sigma σ no longer extends to an automorphism, since σ ( R h ( γ 4 S ) ) = { σ γ 7 } ≠ ∅ = R h ( σ γ 4 S ) \sigma(R_h(\gamma_4^S))=\{\sigma\gamma_7\}\ne\varnothing=R_h(\sigma\gamma_4^S) σ ( R h ( γ 4 S )) = { σ γ 7 } = ∅ = R h ( σ γ 4 S ) would be required. The distinction also survives under bisimulation: γ 4 S \gamma_4^S γ 4 S has an h h h -move and γ 4 W \gamma_4^W γ 4 W does not, so the two are no longer bisimilar. The added structure therefore breaks the symmetry and supplies a structural distinction that the coarse representation lacked; this is the first of the ways out described in § 5 . This is the limit of what the coarse representation can decide, not a claim that the two characteristics are identical in every richer description.
A refinement that separates the two only by multiplicity is weaker. If instead R h ( γ 4 S ) = { γ 7 S , γ 7 S ′ } R_h(\gamma_4^S) = \{\gamma_7^S,\gamma_7^{S'}\} R h ( γ 4 S ) = { γ 7 S , γ 7 S ′ } and R h ( γ 4 W ) = { γ 7 W } R_h(\gamma_4^W) = \{\gamma_7^W\} R h ( γ 4 W ) = { γ 7 W } with the three targets terminal, the symmetry σ \sigma σ is again broken and the status-equivalence class is split (diluted versus preserved), but γ 4 S \gamma_4^S γ 4 S and γ 4 W \gamma_4^W γ 4 W remain bisimilar. Whether a difference in the number of structurally identical descendants should count as a distinction for recognition is a normative choice that this paper does not make, and the refinement above does not depend on it.
Recoverability and Its Computational Limits
Sections 4 and 5 concern the choice among successors. This section asks what remains possible after a recognition has failed: whether the structure still offers a route to correct it, and how hard that is to decide.
Under the full-realization baseline of the main text, for every state x x x reached by a finite history ρ \rho ρ , D ρ r e ( x ) = D ( x ) D^{\mathrm{re}}_{\rho}(x) = D(x) D ρ re ( x ) = D ( x ) , and R p r e = R p R^{\mathrm{re}}_p = R_p R p re = R p for every path segment p p p along ρ \rho ρ ; the realized variants and the determination process that prunes them are treated in Appendix § 14 , and the cut number of § 8 measures how robust the conditions below are to partial realization.
The section introduces its objects in the following order. First, failure events, which are exclusion events and lineage-death events, and the set F ( ρ ) F(\rho) F ( ρ ) of those generated along a history. Second, three predicates on a corrective transition: structural eligibility, admissible correction, and completed correction, where completed correction implies admissible correction, which implies structural eligibility. Third, the set U ( ρ ) U(\rho) U ( ρ ) of unresolved failure events (exclusion events not yet corrected, together with every lineage-death event). Fourth, system-level recoverability: extensions of a history, corrective-route witnesses, and the predicate Recover a v a i l \operatorname{Recover}_{\mathrm{avail}} Recover avail , which asks whether some extension of this history offers a corrective route for every unresolved exclusion, and is determined by a finite prefix. Fifth, trace recoverability Recover t r a c e \operatorname{Recover}_{\mathrm{trace}} Recover trace , which asks whether, along an infinite history, every exclusion is eventually corrected, together with the proposition separating it from Recover a v a i l \operatorname{Recover}_{\mathrm{avail}} Recover avail . The last subsection classifies the cost of deciding these predicates.
A failure event is generated at a stage of some finite history. An exclusion event is a pair ( ρ e , γ ) (\rho_e,\gamma) ( ρ e , γ ) , where ρ e \rho_e ρ e is the finite history at whose end stage the coordinate γ \gamma γ lies in D ρ e r e ( x ) D^{\mathrm{re}}_{\rho_e}(x) D ρ e re ( x ) and
B ρ e ( x ) ( γ ) = E . B_{\rho_e}(x)(\gamma) = \mathrm{E}. B ρ e ( x ) ( γ ) = E .
A lineage-death event is a pair ( ρ e , γ 0 ) (\rho_e,\gamma_0) ( ρ e , γ 0 ) , where γ 0 ∈ I 0 \gamma_0 \in I_0 γ 0 ∈ I 0 and ρ e \rho_e ρ e ends at the first stage at which L i ( γ 0 ) = ∅ L_i(\gamma_0) = \varnothing L i ( γ 0 ) = ∅ under the stipulated structure. The subscript e e e records the generating history and fixes the event’s identity. For a finite history ρ \rho ρ , let F ( ρ ) F(\rho) F ( ρ ) be the set of failure events generated at some prefix of ρ \rho ρ :
F ( ρ ) = { e : ρ e ⪯ ρ and e is generated at ρ e } . F(\rho) = \{e : \rho_e \preceq\rho\text{ and } e \text{ is generated at } \rho_e\}. F ( ρ ) = { e : ρ e ⪯ ρ and e is generated at ρ e } .
Then ρ ⪯ ρ ′ \rho\preceq\rho' ρ ⪯ ρ ′ implies F ( ρ ) ⊆ F ( ρ ′ ) F(\rho) \subseteq F(\rho') F ( ρ ) ⊆ F ( ρ ′ ) . An exclusion event is generated at the first prefix at which the relevant recognition state assigns emptiness E; a lineage-death event is generated at the first stage at which the stipulated lift becomes empty.
Lineage death. Once L i ( γ 0 ) = ∅ L_i(\gamma_0) = \varnothing L i ( γ 0 ) = ∅ we have R p ( γ 0 ) = ∅ R_p(\gamma_0) = \varnothing R p ( γ 0 ) = ∅ for every stipulated path p p p extending the prefix through that stage, because R ( ∅ ) = ∅ R(\varnothing) = \varnothing R ( ∅ ) = ∅ . A lineage-death event admits no corrective inscription along extensions of that prefix. The qualification is relative to the fixed ( C , R ) (C,R) ( C , R ) and the realized history: a different history that diverged earlier, or a later re-stipulation of ( C , R ) (C,R) ( C , R ) , is outside the claim. A structurally dead lineage can reappear if the representation is re-stipulated or if a different history reaches the same property by another route, and the framework records the revival as a new inscription under the new representation rather than as a corrective inscription under the old one. Death is defined only for continuations in the initial inscription I 0 I_0 I 0 ; a lineage that is not in I 0 I_0 I 0 can lose every corrective route without being dead, and the monotone, irreversible part of Recovera v a i l _{\mathrm{avail}} avail depends on this choice. Extending death to an arbitrary realized coordinate would strengthen the predicate’s negative case at the cost of an additional initial condition.
Exclusion and the three predicates. If ( ρ e , γ ) (\rho_e,\gamma) ( ρ e , γ ) is an exclusion event at state x x x , a corrective inscription may occur later along an extension. Three predicates are distinguished. Structural eligibility: some δ \delta δ lies in R p r e ( γ ) R^{\mathrm{re}}_p(\gamma) R p re ( γ ) for a path segment p p p from x x x to a later state y y y . Admissible correction: δ \delta δ is realized, lies in D ρ j r e ( y ) D^{\mathrm{re}}_{\rho_j}(y) D ρ j re ( y ) , remains U immediately before the transition, and satisfies S ( y , δ ) = i n s c r i b e d S(y,\delta) = \mathrm{inscribed} S ( y , δ ) = inscribed . Completed correction: the recognition history records the transition U → \to → I at δ \delta δ . Under the same event, descendant, and history parameters, completed correction implies admissible correction, which in turn implies structural eligibility; neither converse holds. Structural eligibility does not establish that the descendant is realized, belongs to the decision domain, or is admissible under S S S . Admissibility does not establish that the transition actually occurs. The illustration at the end of this section exhibits all three predicates in a single case.
Unresolved events. An exclusion event is resolved on a finite history once a completed correction has occurred. It remains in F ( ρ ) F(\rho) F ( ρ ) but leaves the set U ( ρ ) ⊆ F ( ρ ) U(\rho) \subseteq F(\rho) U ( ρ ) ⊆ F ( ρ ) of unresolved events. A lineage-death event is never resolved, so every lineage-death event in F ( ρ ) F(\rho) F ( ρ ) lies in U ( ρ ) U(\rho) U ( ρ ) . For an infinite history τ \tau τ , let
F ( τ ) = ⋃ i F ( τ ∣ i ) , F(\tau) = \bigcup_i F(\tau\mathbin{|}i), F ( τ ) = i ⋃ F ( τ ∣ i ) ,
where only finite prefixes occur in this definition.
System-level recoverability. Fix an unresolved exclusion event e = ( ρ e , γ ) ∈ U ( ρ ) e = (\rho_e,\gamma) \in U(\rho) e = ( ρ e , γ ) ∈ U ( ρ ) at state x x x ; note ρ e ⪯ ρ \rho_e \preceq\rho ρ e ⪯ ρ . An extension of ρ \rho ρ is a pair consisting of a generating history ρ ′ ⪰ ρ \rho' \succeq\rho ρ ′ ⪰ ρ and an admissible recognition continuation: coordinates decided in ρ \rho ρ keep their values, and every recognition event in ρ ′ \rho' ρ ′ beyond ρ \rho ρ is a U → S ^ \to\widehat{\mathrm{S}} → S transition. Availability is thus an optimistic notion: it asks whether the corrective transitions can be taken, not whether they will be.
A corrective-route witness for e e e on ρ ′ \rho' ρ ′ is a pair ( η , δ ) (\eta,\delta) ( η , δ ) with ρ ⪯ η ⪯ ρ ′ \rho\preceq\eta\preceq\rho' ρ ⪯ η ⪯ ρ ′ , η \eta η ending at y y y , and, for the segment p : x ⇝ y p : x \rightsquigarrow y p : x ⇝ y along ρ ′ \rho' ρ ′ ,
δ ∈ R p ( γ ) ∩ D ( y ) , B η ( y ) ( δ ) = U , S ^ ( y , δ ) = I . \delta\in R_p(\gamma) \cap D(y), \qquad B_\eta(y)(\delta) = \mathrm{U}, \qquad\widehat{S}(y,\delta) = \mathrm{I}. δ ∈ R p ( γ ) ∩ D ( y ) , B η ( y ) ( δ ) = U , S ( y , δ ) = I .
Requiring η ⪰ ρ \eta\succeq\rho η ⪰ ρ (rather than η ⪰ ρ e \eta\succeq\rho_e η ⪰ ρ e ) excludes opportunities that the history has already passed. Under the realized definitions of Appendix C, also require δ \delta δ to belong to the realized lift and realized decision domain at η \eta η . Write W e ( ρ ′ ) W_e(\rho') W e ( ρ ′ ) for the set of witnesses for e e e on ρ ′ \rho' ρ ′ ; for a lineage-death event e e e no witness exists and W e ( ρ ′ ) = ∅ W_e(\rho') = \varnothing W e ( ρ ′ ) = ∅ . A witness establishes that an admissible corrective transition is available.
Throughout, ( H , C , R ) (H,C,R) ( H , C , R ) , the determination process, and S S S remain fixed. For a finite history ρ \rho ρ , define
Recover a v a i l ( ρ ) ⟺ ∃ ρ ′ ⪰ ρ : ( no lineage-death event lies in F ( ρ ′ ) ) ∧ ∀ e ∈ U ( ρ ) : W e ( ρ ′ ) ≠ ∅ . (26) \operatorname{Recover}_{\mathrm{avail}}(\rho) \Longleftrightarrow\exists\rho' \succeq\rho: \left(\text{no lineage-death event lies in } F(\rho')\right) \land\forall e \in U(\rho): W_e(\rho') \ne\varnothing. \tag*{(26)} Recover avail ( ρ ) ⟺ ∃ ρ ′ ⪰ ρ : ( no lineage-death event lies in F ( ρ ′ ) ) ∧ ∀ e ∈ U ( ρ ) : W e ( ρ ′ ) = ∅ . (26)
One extension must contain a witness for each unresolved exclusion. This is simultaneous availability along a common extension. The witnessing extension must itself be free of lineage-death events, so a correction that is available only by killing a lineage in I 0 I_0 I 0 does not count. A lineage-death event makes the predicate false; the quantifier does not range over alternative determination processes or criteria. Death-freeness over all of F ( ρ ′ ) F(\rho') F ( ρ ′ ) is equivalent to death-freeness up to the last witnessing prefix: if ρ ′ \rho' ρ ′ witnesses every event of U ( ρ ) U(\rho) U ( ρ ) , truncating it at its last witnessing prefix keeps every witness, since a witness depends only on the history up to η \eta η , and cannot introduce a death event, since F F F is monotone under prefixes, so the two readings coincide.
The predicate is monotone decreasing under history extension: once it fails it fails on every extension. The reason is that a witnessing extension for a later prefix also witnesses every event still unresolved at the earlier prefix, and events resolved in between were resolved by a completed correction, which is itself a witness. A lineage-death event can enter U U U and can never leave, which is the second way the predicate is lost. The precise statement and proof are given in the remark below.
Proof. Let ρ ′ ′ ⪰ ρ ′ \rho'' \succeq\rho' ρ ′′ ⪰ ρ ′ witness ρ ′ \rho' ρ ′ . It is death-free, and ρ ′ ′ ⪰ ρ \rho'' \succeq\rho ρ ′′ ⪰ ρ , so it is also an admissible candidate for ρ \rho ρ . Take e ∈ U ( ρ ) e \in U(\rho) e ∈ U ( ρ ) . If e ∈ U ( ρ ′ ) e \in U(\rho') e ∈ U ( ρ ′ ) , it has a witness on ρ ′ ′ \rho'' ρ ′′ with η ⪰ ρ ′ ⪰ ρ \eta\succeq\rho' \succeq\rho η ⪰ ρ ′ ⪰ ρ . Otherwise e e e was resolved on ρ ′ \rho' ρ ′ by a completed correction at some η ⪰ ρ \eta\succeq\rho η ⪰ ρ , where η \eta η is the prefix immediately before the transition, so that the coordinate is still U at η \eta η ; since completed correction implies admissible correction, ( η , δ ) (\eta,\delta) ( η , δ ) is a witness on ρ ′ ′ \rho'' ρ ′′ . Hence ρ ′ ′ \rho'' ρ ′′ witnesses every event of U ( ρ ) U(\rho) U ( ρ ) . The predicate can be lost in two ways: a lineage-death event enters U U U , or the history commits to a branch that forecloses a route some unresolved exclusion needed. It cannot be regained, because choosing one branch does not make an incompatible branch available. □
Trace recoverability. For an infinite history τ \tau τ , define
Recover t r a c e ( τ ) ⟺ ∀ e ∈ F ( τ ) , ∃ i such that e ∈ F ( τ ∣ i ) ∖ U ( τ ∣ i ) . (27) \operatorname{Recover}_{\mathrm{trace}}(\tau) \Longleftrightarrow\forall e \in F(\tau),\ \exists i\ \text{such that}\ e \in F(\tau|i) \setminus U(\tau|i). \tag*{(27)} Recover trace ( τ ) ⟺ ∀ e ∈ F ( τ ) , ∃ i such that e ∈ F ( τ ∣ i ) ∖ U ( τ ∣ i ) . (27)
Every object appearing here is indexed by a finite prefix. This says that every failure that occurs along τ \tau τ is eventually resolved along that same history. Requiring e ∈ F ( τ ∣ i ) e \in F(\tau|i) e ∈ F ( τ ∣ i ) matters: since U ( τ ∣ i ) ⊆ F ( τ ∣ i ) U(\tau|i) \subseteq F(\tau|i) U ( τ ∣ i ) ⊆ F ( τ ∣ i ) , the bare condition e ∉ U ( τ ∣ i ) e \notin U(\tau|i) e ∈ / U ( τ ∣ i ) holds trivially at every prefix before e e e is generated. Since a lineage-death event is never resolved, the predicate fails whenever τ \tau τ contains one; if no failure occurs, it holds vacuously.
Write P \mathcal{P} P for the set of infinite histories satisfying Recover t r a c e \operatorname{Recover}_{\mathrm{trace}} Recover trace . Three facts hold, and none needs the Alpern–Schneider decomposition [12 ] , which in general writes any property as the intersection of a safety property and a liveness property. First, a lineage-death event is irrevocable: a finite prefix that contains one has no extension in P \mathcal{P} P , so such prefixes are bad prefixes of P \mathcal{P} P . Second, P \mathcal{P} P need not be a safety property: in structures with the hypothesis of Remark 7, no death-free prefix certifies membership. Third, a finite prefix ρ \rho ρ lies in the safety closure of P \mathcal{P} P iff some infinite history τ ⪰ ρ \tau\succeq\rho τ ⪰ ρ , with an admissible recognition continuation, contains no lineage-death event and resolves every event in F ( τ ) F(\tau) F ( τ ) . Hence Recover a v a i l ( ρ ) \operatorname{Recover}_{\mathrm{avail}}(\rho) Recover avail ( ρ ) is necessary for membership in the closure, and sufficient only when a witnessing extension can be continued indefinitely without death and the witnessed corrections are performed. We do not claim that the three requirements one can read off the definition (no death, retention of a route, eventual resolution) correspond to the safety and liveness factors of that decomposition.
The gap between availability at every prefix and resolution on the trace is therefore not a discovery about the formalism; it is a fairness assumption on the exogenous recognition history. The framework does not force corrections to occur. What it can say is the following: a corrective route can exist at every finite stage, yet the recognition history may never take it.
Proposition 7 (Availability versus occurrence). Availability at every prefix does not imply trace recoverability: there are structures (those containing a repeatable corrective route, Appendix B.3) with an infinite history τ \tau τ such that Recover a v a i l ( τ ∣ i ) \operatorname{Recover}_{\mathrm{avail}}(\tau|i) Recover avail ( τ ∣ i ) holds for every finite prefix τ ∣ i \tau|i τ ∣ i ,
yet Recover t r a c e ( τ ) \operatorname{Recover}_{\mathrm{trace}}(\tau) Recover trace ( τ ) fails. Conversely, suppose the structure has finitely many coordinates, the recognition history is strongly fair (a transition admissible infinitely often is eventually taken), τ \tau τ contains no lineage-death event, and a witness for each exclusion e ∈ F ( τ ) e \in F(\tau) e ∈ F ( τ ) keeps recurring along τ \tau τ for as long as e e e is unresolved (for every i i i with e ∈ U ( τ ∣ i ) e \in U(\tau|i) e ∈ U ( τ ∣ i ) there are j ≥ i j \ge i j ≥ i and a witness ( τ ∣ j , δ ) (\tau|j,\delta) ( τ ∣ j , δ ) for e e e ). Then Recover t r a c e ( τ ) \operatorname{Recover}_{\mathrm{trace}}(\tau) Recover trace ( τ ) holds.
Proof. The negative direction is the construction of Appendix § 13 .§ 3 ; the positive direction follows from strong fairness and is proved in the same appendix.
Remark 7 (A finite prefix does not settle trace recoverability). With ( H , C , R ) (H,C,R) ( H , C , R ) , D D D , S S S and the determination rule fixed and known, Recover a v a i l ( ρ ) \operatorname{Recover}_{\mathrm{avail}}(\rho) Recover avail ( ρ ) is determined by ρ \rho ρ and is decidable (Proposition 10 ). What a prefix cannot settle is the trace-level outcome, which depends on which future occurs and on whether the recognition history takes an available correction. A prefix containing a lineage-death event does falsify trace recoverability; under the hypothesis below, a death-free prefix cannot certify it.
The asymmetry can be constructed explicitly under a hypothesis on the structure: it must contain neutral modifications that can be repeated indefinitely (for instance a self-loop on a state whose fiber carries no descendants of the excluded coordinate), since in a finite acyclic structure every history is finite. Fix a prefix ρ \rho ρ ending with an unresolved exclusion event e e e . Consider two infinite extensions τ 1 , τ 2 \tau_1,\tau_2 τ 1 , τ 2 that agree on a common extension of ρ \rho ρ for n n n stages for arbitrarily large n n n , obtained by n n n neutral modifications that do not touch the eligible descendants of the excluded coordinate, and then diverge: τ 1 \tau_1 τ 1 reaches a realized, inscribable, and actually inscribed descendant, resolving e e e ; τ 2 \tau_2 τ 2 routes through modifications whose relations send the image of the excluded coordinate to ∅ \varnothing ∅ on every branch from the divergence point onward, so e e e is never resolved. The second step forecloses the route for e e e ; it is not a lineage-death event, since death is defined only for γ 0 ∈ I 0 \gamma_0 \in I_0 γ 0 ∈ I 0 . Since n n n is arbitrary, no finite prefix distinguishes the two futures. The construction is given in full in Appendix § 13 .
On falsification and verification. A corrective inscription is an explicit recognition event. It enters the completed recognition record through the recognition history that records it.
Illustration of the three predicates. The extension used here is schematic and not drawn from the seven-state core system, whose decision domain is empty after x 4 x_4 x 4 and so offers no corrective route to illustrate; it illustrates the three predicates in a single case without computing from the core model. Consider an extension of the core system containing a state x 10 x_{10} x 10 , and let ρ 10 \rho_{10} ρ 10 be a finite history from x 0 x_0 x 0 to x 10 x_{10} x 10 in it (the extension is not drawn). Suppose that ρ 10 \rho_{10} ρ 10 contains exactly one unresolved exclusion event ( ρ 10 , γ 10 ) (\rho_{10},\gamma_{10}) ( ρ 10 , γ 10 ) and no lineage-death events:
B ρ 10 ( x 10 ) ( γ 10 ) = E . B_{\rho_{10}}(x_{10})(\gamma_{10}) = \mathrm{E}. B ρ 10 ( x 10 ) ( γ 10 ) = E .
A subsequent modification r : x 10 → x 13 r:x_{10}\to x_{13} r : x 10 → x 13 satisfies
R r ( γ 10 ) = { γ 13 S } . (28) R_r(\gamma_{10}) = \{\gamma_{13}^{S}\}. \tag*{(28)} R r ( γ 10 ) = { γ 13 S } . (28)
If γ 13 S \gamma_{13}^{S} γ 13 S is realized, belongs to the realized decision domain, remains U when x 13 x_{13} x 13 is reached, and S ( x 13 , γ 13 S ) = I S(x_{13},\gamma_{13}^{S})=\mathrm{I} S ( x 13 , γ 13 S ) = I , then the extension offers a corrective route for the unique unresolved exclusion event. Since there are no lineage-death events and no other unresolved exclusions, this suffices to establish Recover a v a i l ( ρ 10 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_{10}) Recover avail ( ρ 10 ) for this example. If the corrective transition occurs, then for the next prefix ρ 13 \rho_{13} ρ 13 ,
B ρ 13 ( x 13 ) ( γ 13 S ) = I , B_{\rho_{13}}(x_{13})(\gamma_{13}^{S}) = \mathrm{I}, B ρ 13 ( x 13 ) ( γ 13 S ) = I ,
and the exclusion event is resolved. The prefix ρ 10 \rho_{10} ρ 10 alone does not establish that the route will occur.
Had the lineage of γ 0 \gamma_0 γ 0 instead died at some stage of ρ 10 \rho_{10} ρ 10 , the corresponding lineage-death event would remain unresolved on every extension of that prefix, and Recover a v a i l ( ρ 10 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_{10}) Recover avail ( ρ 10 ) would fail regardless of the corrective route for the exclusion event.
Computational limits on deciding persistence and recoverability
The following complexity results use the extensional finite input specified below; proof sketches are provided, with full derivations for the Recover a v a i l \operatorname{Recover}_{\mathrm{avail}} Recover avail classification in Appendix B.
Fix a finite generating graph: a finite set of states, a finite set of elementary modifications between them, and the compatibility relations attached to those elementary modifications. The continuation fibers are finite, and both the fibers and the relations are given extensionally : each fiber is listed as a finite set, and each relation is listed as a finite set of pairs. This is the input; complexity is measured in its size. Composite modifications and their relations are induced by the composition condition of Section 2 and are not part of the input. All reductions below respect the composition condition of Section 2.
The recoverability classifications below are stated for a restricted model in which realization is state-determined: the determination rule Δ \Delta Δ is a function of the state reached alone, so that two paths reaching the same state carry the same realized subset there. This restricts the general definition of Appendix C, in which realization is history-indexed; that general definition is retained, but the complexity theorems are claimed only for the restricted model. The extensional instance includes an effective representation of Δ \Delta Δ , and evaluating it must take polynomial time in the size of the instance. The decision domain and recognition criterion are given extensionally, so their membership tests are also polynomial-time. The polynomial-time requirement is used for the NP upper bound in the acyclic case, where the certificate is a path; the PSPACE upper bound in the general case needs only polynomial-space evaluability of Δ \Delta Δ , as explained below. An unencoded or oracle-supplied rule is not covered. Under this restriction, the search configuration described in Appendix B determines the realized witnesses of a path. The classifications are therefore relative to this effective-representation requirement.
In realistic applications the fibers are implicit and large, so the classifications below describe worst-case behavior of a worst-case encoding, not the cost of auditing a deployed system. Under an implicit encoding, such as fibers described by circuits or by grammars, the input size is the size of the description rather than the number of elements, the upper bounds change accordingly, and the lower bounds are not guaranteed to survive: the reductions construct explicit fibers, and a compact description of the same structure might avoid the NP- or PSPACE-hard instances. The classification is therefore about the intrinsic difficulty of the decision problems as posed on an explicit representation of the restricted model, and its transfer to implicitly represented systems or to arbitrary history-indexed realization is not established here. The explicit-encoding classifications are therefore a baseline: they say what the problems cost on the encoding the paper specifies, and they do not by themselves settle the cost on any other encoding.
The decision problems. The classifications below concern three decision problems.
Dilution-existence. Given a finite generating graph with finite fibers and extensional compatibility relations, an initial continuation γ 0 ∈ C ( x 0 ) \gamma_0 \in C(x_0) γ 0 ∈ C ( x 0 ) , does there exist a finite path beginning at x 0 x_0 x 0 along which the stipulated lift of γ 0 \gamma_0 γ 0 becomes diluted?
Death-existence. Given the same input, does there exist a finite path beginning at x 0 x_0 x 0 along which the stipulated lift of γ 0 \gamma_0 γ 0 becomes empty? Its complement is the death-freeness problem .
Recover_avail. Given the same input together with an effective representation of the state-determined realization rule Δ \Delta Δ , a decision domain D D D , a recognition criterion S S S , an initial inscription I 0 I_0 I 0 , and a finite history ρ \rho ρ with a set U ( ρ ) U(\rho) U ( ρ ) of unresolved failure events, does Recover a v a i l ( ρ ) \operatorname{Recover}_{\mathrm{avail}}(\rho) Recover avail ( ρ ) hold?
Complexity classes are used in the standard sense [13 ] . The reductions below are classical many-one reductions from NFA and CNF problems, in view of the correspondence with nondeterministic automata in § 2 . NFA-intersection-nonemptiness is PSPACE-complete [14 ] ; NFA universality is PSPACE-complete [15 ] . The two are not equivalent formulations, and the reductions below use each where it is directly applicable.
The upper bounds are stated for an explicit encoding with an effectively evaluable determination rule. In the acyclic case the natural certificate is a path, verified by step-by-step evaluation, which requires polynomial-time evaluability. In the general case the natural certificate is a search configuration, verified by simulation with a counter, which requires only polynomial-space evaluability. The difference between the two assumptions is a consequence of the certificate type, not of the problem: a path could also be verified by simulation, at the cost of a weaker bound subsumed by the general case. For an arbitrary exogenous Δ \Delta Δ the decision problems may be undecidable, and the classifications are relative to the effective representation.
Proposition 8 (Dilution-existence is NL-complete). Dilution-existence is NL-complete under logspace reductions.
Proof. See Appendix § 12 : membership is reachability in a square graph of pairs of continuations, and hardness reduces from s s s –t t t reachability.
Proposition 9 (Death-existence). For the explicit finite encoding, death-existence is NP-complete for acyclic H H H and PSPACE-complete for general H H H . Its complement, death-freeness, is coNP-complete for acyclic H H H and PSPACE-complete in general.
Proof. See Appendix § 12 . The acyclic case reduces from CNF satisfiability and the general case from NFA non-universality [15 ] .
Proposition 10 (Recover avail classification in the restricted model). For the explicit finite encoding with state-determined, polynomial-time evaluable realization rule specified above, R e c o v e r a v a i l Recover_{\mathrm{avail}} R eco v e r avail is NP-complete for acyclic H H H and PSPACE-complete for general H H H . The general history-indexed realization model of Appendix § 14 is not covered by this classification.
Proof. See Appendix § 13 , which gives both reductions (from CNF satisfiability and from NFA-intersection nonemptiness) in full, with both directions of each correspondence and the membership arguments.
Remark 8. The two classifications above have the same shape: NP-complete for acyclic H H H , PSPACE-complete for general H H H . The similarity reflects the common underlying difficulty: in both cases, deciding whether a structural configuration exists requires exploring a family of paths whose choices interact globally.
Reading. Existential dilution along some finite history is NL-complete. In the acyclic case, death-existence is NP-complete, and consequently death-freeness, its complement, is coNP-complete. In the general case, death-existence is PSPACE-complete and death-freeness is coPSPACE-complete, which coincides with PSPACE because PSPACE is closed under complement. R e c o v e r a v a i l Recover_{\mathrm{avail}} R eco v e r avail follows the same pattern: NP-complete for acyclic H H H and PSPACE-complete for general H H H . The pattern is not an artifact of the two cases being treated separately: the same problem is hard for the same reason in both, and the difference between NP and PSPACE reflects the difference between a path certificate and a walk certificate, which in turn reflects the difference between an acyclic structure, where every walk is a path, and a general structure, where walks may revisit configurations.
What the classification does and does not say. Recoveravail is largely a reachability question about S S S . The criterion sanctions both the exclusion and the later inscription, no excluded coordinate is ever overturned (it stays E), and a “failure event” is an exclusion event as recorded, not an inadmissible decision. The hardness in both reductions comes from the conjunction over many unresolved exclusions; with a single event the problem reduces to reachability of a coordinate in the lift graph. The quantifier is also optimistic: Recoveravail asks whether some good extension exists. A guarantee against unknown or adversarial futures is a universal or game-theoretic question; death-freeness is its counterpart for lineage death, and a universal analogue of Recoveravail is not studied here. The results bear on the cost of deciding these predicates, not on guarantees an auditor could obtain. The classifications hold for the restricted model and the explicit encoding. Extending them to the general history-indexed realization model, and to systems whose fibers are implicit and whose determination rule may not be effectively evaluable, is left open.
Realization and the Cut Number
The preceding sections evaluate lifts in the stipulated structure. This section asks what changes when a history realizes only part of it.
The stipulated structure fixes C ( x ) C(x) C ( x ) and R f R_f R f . A conformance determination records which stipulated continuations a history actually realizes. A determination rule Δ \Delta Δ assigns to each finite history prefix π \pi π ending at x i x_i x i a realized subset C i r e ⊆ C ( x i ) C_i^{\mathrm{re}} \subseteq C(x_i) C i re ⊆ C ( x i ) , with C 0 r e = C ( x 0 ) C_0^{\mathrm{re}} = C(x_0) C 0 re = C ( x 0 ) . The realized lifts are
L 0 r e ( γ 0 ) = { γ 0 } , L i r e ( γ 0 ) = R f i ( L i − 1 r e ( γ 0 ) ) ∩ C i r e . L_0^{\mathrm{re}}(\gamma_0) = \{\gamma_0\}, \qquad L_i^{\mathrm{re}}(\gamma_0) = R_{f_i}\bigl(L_{i-1}^{\mathrm{re}}(\gamma_0)\bigr) \cap C_i^{\mathrm{re}}. L 0 re ( γ 0 ) = { γ 0 } , L i re ( γ 0 ) = R f i ( L i − 1 re ( γ 0 ) ) ∩ C i re .
Realization cannot create a branch absent from the stipulated structure, and the realized relation does not itself obey a composition law. Realization is history-indexed in general, and the complexity results of § 7.1 cover only the restricted model in which it is state-determined and effectively evaluable.
Along a fixed history ρ \rho ρ , the path graph G ρ ( γ 0 ) G_\rho(\gamma_0) G ρ ( γ 0 ) has the vertices ( i , ε ) (i,\varepsilon) ( i , ε ) with ε ∈ L i ( γ 0 ) \varepsilon\in L_i(\gamma_0) ε ∈ L i ( γ 0 ) and an edge ( i − 1 , ε ) → ( i , ε ′ ) (i-1,\varepsilon) \to(i,\varepsilon') ( i − 1 , ε ) → ( i , ε ′ ) whenever ε ′ ∈ R f i ( ε ) \varepsilon' \in R_{f_i}(\varepsilon) ε ′ ∈ R f i ( ε ) . The realization-cut number κ n ( γ 0 ) \kappa_n(\gamma_0) κ n ( γ 0 ) is the least number of vertices, other than the root, whose non-realization empties the realized lift. By Menger’s theorem it equals the maximum number of paths to layer n n n that are vertex-disjoint except at the root, so it is computable by max-flow; and 1 ≤ κ n ( γ 0 ) ≤ min 1 ≤ i ≤ n ∣ L i ( γ 0 ) ∣ 1 \le\kappa_n(\gamma_0) \le\min_{1 \le i \le n} |L_i(\gamma_0)| 1 ≤ κ n ( γ 0 ) ≤ min 1 ≤ i ≤ n ∣ L i ( γ 0 ) ∣ (Proposition 12). It refines the three statuses: two diluted lineages with the same lift sizes can have different cut numbers (Example 2). In the abstract model of § 6 , γ 0 \gamma_0 γ 0 is diluted along P A P_A P A but has κ 5 ( γ 0 ) = 1 \kappa_5(\gamma_0)=1 κ 5 ( γ 0 ) = 1 , as fragile as a preserved lineage, whereas the lineage of γ 2 \gamma_2 γ 2 alone along ( d , f , g ) (d,f,g) ( d , f , g ) has κ = 2 \kappa=2 κ = 2 . The cut number is a worst-case combinatorial quantity. Reading it as tolerance to failure needs an extra assumption on how many vertices the determination process can leave unrealized. Definitions, the proposition with proof, the determination records, the effect of partial realization on underdetermination and on recoverability are in Appendix § 14 .
Discussion
Each result of this study traces to one of the requirements of the Introduction. Requirements (R1)–(R5) make a succession structure simultaneously an object with a group of symmetries, a nondeterministic automaton, and a layered flow network. The relevant results from each theory then apply once the correspondence is established. The symmetry diagnostic and the orbit condition come from the group action. The NL, NP and PSPACE classifications come from the automaton. The cut number comes from the flow network through Menger’s theorem (Appendix § 14 ). It is polynomial-time computable along a fixed path, so hardness enters in choosing which path to take and not in evaluating robustness along one. This is the sense in which the formulation is useful: it places succession questions where a body of theory already exists.
Dependencies that the relational form cannot express directly, such as a joint effect of two co-present continuations, can be encoded by refining the states so that the interaction is fixed at the step where the pair arises (§ 2 ). The class of represented pipelines is therefore as broad as the class whose steps are well defined and either act additively or can be refined to do so, and every result is relative to the granularity chosen for C ( x ) C(x) C ( x ) . The results apply to any representation satisfying the definitions of § 2 –§ 5 , together with the determination rule of § 8 .
Recoverability asks whether some extension of the current history gives every unresolved exclusion a corrective route, so its cost depends on how many histories reach a state and whether states can be re-entered. If every state has one history, the histories are the root-to-node paths of a forest, there are polynomially many, and enumeration decides the question. If states can be reached by several histories, as when two branches merge, the number of histories can be exponential, and the problem is NP-hard already for acyclic structures. If states can also be re-entered, an extension is a walk of unbounded length over configurations of state and lifts, and the problem is PSPACE-complete. These costs are properties of the structure and not of any implementation: they follow from the two composition conditions and a few general assumptions alone, and they apply to every system that meets those conditions, whatever its ledger, runtime or storage.
The recent study of Zhu and Wang [19 ] on authorization for populations of self-modifying AI agents illustrates the contrast. Their protocol stays in the first case by assumption: their A4 gives each generation a unique parent, so the generation graph is a forest with no reconvergence; their A3 and the fresh-generation rollback rule out re-entry; and their A6, the serialized ledger, fixes the realized subset at the commit point, so realization remains a function of the state reached, the condition under which our classification is proved. Each relaxation a deployment tends to make moves the problem up a tier: a permitted merge introduces reconvergence; restoring a generation without a fresh identity introduces cycles; and a sharded ledger makes realization depend on commit visibility, which leaves the state-determined model altogether. Each gives up a restriction the protocol adopts for safety, in exchange for scale, availability or flexibility, and the framework says what that costs computationally. The instantiation itself is straightforward; the work lies in the general classification, which makes the contrast visible without reference to any particular implementation.
Possible Extensions Plural succession. A composite source can carry the product of the contributing continuation spaces: for a joining modification m m m with sources x , y x,y x , y and target z z z , set C ( z ) = C ( x ) × C ( y ) C(z)=C(x)\times C(y) C ( z ) = C ( x ) × C ( y ) and R m ⊆ C ( x ) × C ( y ) × C ( z ) R_m\subseteq C(x)\times C(y)\times C(z) R m ⊆ C ( x ) × C ( y ) × C ( z ) . This requires multi-source modifications in the generating graph, a join version of the composition condition, and a reconsideration of whether the persistence statuses extend to a join. Convergence of several continuations onto one would need a classification on the reverse structure.
Continuous settings. The continuation space C ( x ) C(x) C ( x ) could be obtained by thresholding a metric on representations or behaviors: fix a dissimilarity ϱ \varrho ϱ and a threshold λ \lambda λ , and declare two behaviors the same continuation when ϱ ≤ λ \varrho\leq\lambda ϱ ≤ λ . The threshold is a governance act of the same kind as the choice of D D D : a coarser threshold collapses distinct behaviors, and a finer one classifies almost every modification as branching. Exact symmetries would arise from literal copies of the same weights before any divergence; runs with the same recipe but different seeds or data order are at best approximately similar, and whether thresholding makes them isomorphic is an empirical question.
Conclusion
The framework developed here formalizes succession in terms of possible continuations, compatibility, and realization. Its connection to graph and automaton theories makes it possible to analyze structural persistence, recoverability, finite observation, computational complexity, and the effects of partial realization. These results establish what can be determined from a specified structure without committing to a particular criterion of identity or succession.
The analysis nevertheless depends on stipulating the continuation spaces C ( x ) C(x) C ( x ) and compatibility relations R f R_f R f , subject to conditions such as functoriality and additivity. These conditions enable the formal analysis but may restrict its practical applicability: the framework does not derive the required structure from the transformation process itself. Whether a more general approach can preserve analytical rigor while requiring fewer stipulations remains an open question.
The difficulty of formalizing individuality and succession has a long history. For artificial systems, one possibility is to approach the problem from the opposite direction: rather than reconstructing the relevant structure after transformations occur, one can design systems whose architectures and transformation procedures make their continuities and branching relations explicit. In the terms of this paper, the stipulation of C ( x ) C(x) C ( x ) and R f R_f R f stops being an assumption when these are produced by the construction of the system itself. Whether this approach can provide a more general foundation for analyzing succession, with fewer restrictions on its application, remains to be investigated.
Acknowledgment
This preprint is based upon work supported by Laboratory Directed Research and Development (LDRD) funding from Argonne National Laboratory, provided by the Director, Office of Science, of the U.S. Department of Energy under Contract No. DE-AC02-06CH11357. The U.S. Government retains for itself, and others acting on its behalf, a paid-up nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government.
Proofs of the Complexity Results
This appendix proves Propositions 8 and 9 . The input is as in § 7.1 : a finite generating graph with finite fibers and extensional compatibility relations; composite modifications and their relations are induced by functoriality and are not part of the input. Write c = max x ∣ C ( x ) ∣ c = \max_x |C(x)| c = max x ∣ C ( x ) ∣ . Hardness is under logspace reductions, which are also polynomial-time reductions. All constructions below satisfy additivity, since lifts of sets are formed by union, and satisfy functoriality by definition on the free category of the generating graph.
Lifts as chains
The proposition below is the element-wise form of the identity Eq. (8) of § 3 : the iterated lift is the relation of the composite modification, read one continuation at a time.
Proposition 11 (Chain description of lifts). Let p = ( f 1 , … , f n ) p = (f_1,\ldots,f_n) p = ( f 1 , … , f n ) be a path from x 0 x_0 x 0 and γ 0 ∈ C ( x 0 ) \gamma_0 \in C(x_0) γ 0 ∈ C ( x 0 ) . Then ε ∈ L n ( γ 0 ) \varepsilon\in L_n(\gamma_0) ε ∈ L n ( γ 0 ) if and only if there is a chain γ 0 = ε ( 0 ) , ε ( 1 ) , … , ε ( n ) = ε \gamma_0 = \varepsilon^{(0)},\varepsilon^{(1)},\ldots,\varepsilon^{(n)} = \varepsilon γ 0 = ε ( 0 ) , ε ( 1 ) , … , ε ( n ) = ε with ε ( i ) ∈ R f i ( ε ( i − 1 ) ) \varepsilon^{(i)} \in R_{f_i}(\varepsilon^{(i-1)}) ε ( i ) ∈ R f i ( ε ( i − 1 ) ) for i = 1 , … , n i = 1,\ldots,n i = 1 , … , n . In particular L n ( γ 0 ) ≠ ∅ L_n(\gamma_0) \ne\varnothing L n ( γ 0 ) = ∅ implies L i ( γ 0 ) ≠ ∅ L_i(\gamma_0) \ne\varnothing L i ( γ 0 ) = ∅ for every i ≤ n i \le n i ≤ n .
Proof. For n = 0 n = 0 n = 0 both sides say ε = γ 0 \varepsilon= \gamma_0 ε = γ 0 . Suppose the claim holds for n − 1 n - 1 n − 1 . By Eqs. (6) and (7) , L n ( γ 0 ) = ⋃ ζ ∈ L n − 1 ( γ 0 ) R f n ( ζ ) L_n(\gamma_0) = \bigcup_{\zeta\in L_{n-1}(\gamma_0)} R_{f_n}(\zeta) L n ( γ 0 ) = ⋃ ζ ∈ L n − 1 ( γ 0 ) R f n ( ζ ) , so ε ∈ L n ( γ 0 ) \varepsilon\in L_n(\gamma_0) ε ∈ L n ( γ 0 ) iff ε ∈ R f n ( ζ ) \varepsilon\in R_{f_n}(\zeta) ε ∈ R f n ( ζ ) for some ζ ∈ L n − 1 ( γ 0 ) \zeta\in L_{n-1}(\gamma_0) ζ ∈ L n − 1 ( γ 0 ) , and by the induction hypothesis ζ \zeta ζ is the end of a chain of length n n n , and conversely truncating a chain of length n n n gives one of length n − 1 n-1 n − 1 . The last sentence follows by truncating the chain.
Dilution-existence
Proof of Proposition 8. Reformulation. Define the square graph Λ \Lambda Λ on the vertices ( x , ε 1 , ε 2 ) (x,\varepsilon_1,\varepsilon_2) ( x , ε 1 , ε 2 ) with x ∈ X x \in X x ∈ X and ε 1 , ε 2 ∈ C ( x ) \varepsilon_1,\varepsilon_2 \in C(x) ε 1 , ε 2 ∈ C ( x ) , with an edge ( x , ε 1 , ε 2 ) → ( y , ε 1 ′ , ε 2 ′ ) (x,\varepsilon_1,\varepsilon_2) \to(y,\varepsilon'_1,\varepsilon'_2) ( x , ε 1 , ε 2 ) → ( y , ε 1 ′ , ε 2 ′ ) whenever some modification f : x → y f:x \to y f : x → y satisfies ε 1 ′ ∈ R f ( ε 1 ) \varepsilon'_1 \in R_f(\varepsilon_1) ε 1 ′ ∈ R f ( ε 1 ) and ε 2 ′ ∈ R f ( ε 2 ) \varepsilon'_2 \in R_f(\varepsilon_2) ε 2 ′ ∈ R f ( ε 2 ) . Both coordinates follow the same modification. We claim that γ 0 ∈ C ( x 0 ) \gamma_0 \in C(x_0) γ 0 ∈ C ( x 0 ) is diluted along some finite path from x 0 x_0 x 0 if and only if a vertex ( x , ε 1 , ε 2 ) (x,\varepsilon_1,\varepsilon_2) ( x , ε 1 , ε 2 ) with ε 1 ≠ ε 2 \varepsilon_1 \ne\varepsilon_2 ε 1 = ε 2 is reachable from ( x 0 , γ 0 , γ 0 ) (x_0,\gamma_0,\gamma_0) ( x 0 , γ 0 , γ 0 ) .
Suppose γ 0 \gamma_0 γ 0 is diluted along p = ( f 1 , … , f n ) p=(f_1,\ldots,f_n) p = ( f 1 , … , f n ) . Then ∣ L i ( γ 0 ) ∣ > 1 \lvert L_i(\gamma_0)\rvert>1 ∣ L i ( γ 0 )∣ > 1 for some i i i ; choose two distinct ε 1 , ε 2 ∈ L i ( γ 0 ) \varepsilon_1,\varepsilon_2 \in L_i(\gamma_0) ε 1 , ε 2 ∈ L i ( γ 0 ) . By Proposition 11 each is the end of a chain along ( f 1 , … , f i ) (f_1,\ldots,f_i) ( f 1 , … , f i ) , and the two chains, paired step by step, form a path in Λ \Lambda Λ from ( x 0 , γ 0 , γ 0 ) (x_0,\gamma_0,\gamma_0) ( x 0 , γ 0 , γ 0 ) to ( x i , ε 1 , ε 2 ) (x_i,\varepsilon_1,\varepsilon_2) ( x i , ε 1 , ε 2 ) . Conversely, a path in Λ \Lambda Λ from ( x 0 , γ 0 , γ 0 ) (x_0,\gamma_0,\gamma_0) ( x 0 , γ 0 , γ 0 ) to ( x , ε 1 , ε 2 ) (x,\varepsilon_1,\varepsilon_2) ( x , ε 1 , ε 2 ) determines a sequence of modifications f 1 , … , f n f_1,\ldots,f_n f 1 , … , f n forming a path in H H H from x 0 x_0 x 0 , together with two chains along it, so ε 1 , ε 2 ∈ L n ( γ 0 ) \varepsilon_1,\varepsilon_2 \in L_n(\gamma_0) ε 1 , ε 2 ∈ L n ( γ 0 ) . If ε 1 ≠ ε 2 \varepsilon_1 \ne\varepsilon_2 ε 1 = ε 2 then ∣ L n ( γ 0 ) ∣ > 1 \lvert L_n(\gamma_0)\rvert>1 ∣ L n ( γ 0 )∣ > 1 , and every earlier lift is nonempty by Proposition 11. Hence γ 0 \gamma_0 γ 0 is diluted along ( f 1 , … , f n ) (f_1,\ldots,f_n) ( f 1 , … , f n ) .
Membership in NL. Λ \Lambda Λ has at most ∣ X ∣ c 2 \lvert X\rvert c^2 ∣ X ∣ c 2 vertices, each described by a state and two continuations, that is, in O ( log ∣ X ∣ + log c ) O(\log\lvert X\rvert+\log c) O ( log ∣ X ∣ + log c ) bits. Whether an edge joins two given vertices is tested by scanning the explicit list of modifications and relations, in logarithmic space. The graph is not materialized. Reachability in a graph with such an edge test is in NL, and the target condition ε 1 ≠ ε 2 \varepsilon_1 \ne\varepsilon_2 ε 1 = ε 2 is checked on the current vertex.
NL-hardness. Reduce from directed s s s –t t t reachability. Given a directed graph G = ( V , E ) G=(V,E) G = ( V , E ) and s ≠ t s \ne t s = t , we may assume t t t has no outgoing edge, since deleting such edges does not change whether t t t is reachable from s s s and is a logspace operation. Construct H H H with states V V V and one modification m u v : u → v m_{uv}:u \to v m uv : u → v for each ( u , v ) ∈ E (u,v) \in E ( u , v ) ∈ E . Let C ( s ) = { γ 0 } C(s)=\{\gamma_0\} C ( s ) = { γ 0 } , let C ( v ) = { γ v } C(v)=\{\gamma_v\} C ( v ) = { γ v } for v ∉ { s , t } v \notin\{s,t\} v ∈ / { s , t } (writing γ s = γ 0 \gamma_s=\gamma_0 γ s = γ 0 ), and let C ( t ) = { γ t 1 , γ t 2 } C(t)=\{\gamma_t^1,\gamma_t^2\} C ( t ) = { γ t 1 , γ t 2 } . For an edge ( u , v ) (u,v) ( u , v ) with v ≠ t v \ne t v = t set R m u v ( γ u ) = { γ v } R_{m_{uv}}(\gamma_u)=\{\gamma_v\} R m uv ( γ u ) = { γ v } , and for an edge ( u , t ) (u,t) ( u , t ) set R m u t ( γ u ) = { γ t 1 , γ t 2 } R_{m_{ut}}(\gamma_u)=\{\gamma_t^1,\gamma_t^2\} R m u t ( γ u ) = { γ t 1 , γ t 2 } . Every source continuation is defined, because t t t is a sink and carries no outgoing modification. A finite path in H H H from s s s is a walk in G G G from s s s . Along it every lift is a singleton until the walk reaches t t t , which can happen only at its last step, where the lift has two elements; no lift is ever empty. So γ 0 \gamma_0 γ 0 is diluted along some finite path from s s s if and only if t t t is reachable from s s s . The construction is linear in ∣ G ∣ \lvert G\rvert ∣ G ∣ .
Death-existence
Proof of Proposition 9. Death-existence asks whether some finite path from x 0 x_0 x 0 has L i ( γ 0 ) = ∅ L_i(\gamma_0)=\varnothing L i ( γ 0 ) = ∅ for some i i i . Since R ( ∅ ) = ∅ R(\varnothing)=\varnothing R ( ∅ ) = ∅ , a lift that is empty at some stage is empty at every later stage of the path, so death along a path is equivalent to emptiness of the lift at its last stage.
Membership, acyclic case (NP). In an acyclic graph a path visits distinct states, so it has fewer than ∣ X ∣ \lvert X\rvert ∣ X ∣ modifications. The certificate is a path from x 0 x_0 x 0 . The verifier computes L 1 , L 2 , … L_1,L_2,\ldots L 1 , L 2 , … by the union formula Eq. (7) , scanning the explicit relations at each step, and accepts if some L i L_i L i is empty. This takes time polynomial in the input.
Membership, general case (PSPACE). Call a pair ( x , Γ ) (x,\Gamma) ( x , Γ ) with Γ ⊆ C ( x ) \Gamma\subseteq C(x) Γ ⊆ C ( x ) a configuration. Starting from ( x 0 , { γ 0 } ) (x_0,\{\gamma_0\}) ( x 0 , { γ 0 }) , a modification f : x → y f:x \to y f : x → y moves ( x , Γ ) (x,\Gamma) ( x , Γ ) to ( y , R f ( Γ ) ) (y,R_f(\Gamma)) ( y , R f ( Γ )) , and the lift along a path is the second component of the configuration reached. A configuration is stored in O ( log ∣ X ∣ + c ) O(\log\lvert X\rvert+c) O ( log ∣ X ∣ + c ) bits, and there are at most ∣ X ∣ 2 c \lvert X\rvert2^c ∣ X ∣ 2 c of them. Death occurs along some path if and only if a configuration ( x , ∅ ) (x,\varnothing) ( x , ∅ ) is reachable. A shortest such path visits no configuration twice, so it has at most ∣ X ∣ 2 c \lvert X\rvert2^c ∣ X ∣ 2 c steps. A nondeterministic machine guesses the path one modification at a time, storing the current configuration and a step counter bounded by ∣ X ∣ 2 c \lvert X\rvert2^c ∣ X ∣ 2 c , which takes O ( log ∣ X ∣ + c ) O(\log\lvert X\rvert+c) O ( log ∣ X ∣ + c ) bits, and accepts on reaching an empty second component. This places the problem in NPSPACE, which equals PSPACE by Savitch’s theorem [16 ] .
NP-hardness, acyclic case. Reduce from CNF satisfiability. Let ϕ = C 1 ∧ ⋯ ∧ C m \phi= C_1 \land\cdots\land C_m ϕ = C 1 ∧ ⋯ ∧ C m be a formula with m ≥ 1 m \ge1 m ≥ 1 clauses over variables ν 1 , … , ν k \nu_1,\ldots,\nu_k ν 1 , … , ν k with k ≥ 1 k \ge1 k ≥ 1 . The structure H H H has states s 0 , … , s k + 2 s_0,\ldots,s_{k+2} s 0 , … , s k + 2 and modifications fan : s 0 → s 1 \operatorname{fan}:s_0 \to s_1 fan : s 0 → s 1 , true i , false i : s i → s i + 1 \operatorname{true}_i,\operatorname{false}_i:s_i \to s_{i+1} true i , false i : s i → s i + 1 for i = 1 , … , k i=1,\ldots,k i = 1 , … , k , and t : s k + 1 → s k + 2 t:s_{k+1} \to s_{k+2} t : s k + 1 → s k + 2 . It is acyclic. The fibers are C ( s 0 ) = { γ 0 } \mathcal{C}(s_0)=\{\gamma_0\} C ( s 0 ) = { γ 0 } , C ( s i ) = { ξ 1 ( i ) , … , ξ m ( i ) } \mathcal{C}(s_i)=\{\xi_1^{(i)},\ldots,\xi_m^{(i)}\} C ( s i ) = { ξ 1 ( i ) , … , ξ m ( i ) } for i = 1 , … , k + 1 i=1,\ldots,k+1 i = 1 , … , k + 1 , and C ( s k + 2 ) = { ∗ } \mathcal{C}(s_{k+2})=\{\ast\} C ( s k + 2 ) = { ∗ } . The relations are
R fan ( γ 0 ) = { ξ 1 ( 1 ) , … , ξ m ( 1 ) } , R_{\operatorname{fan}}(\gamma_0)=\{\xi_1^{(1)},\ldots,\xi_m^{(1)}\}, R fan ( γ 0 ) = { ξ 1 ( 1 ) , … , ξ m ( 1 ) } ,
and for each i ∈ { 1 , … , k } i \in\{1,\ldots,k\} i ∈ { 1 , … , k } and j ∈ { 1 , … , m } j \in\{1,\ldots,m\} j ∈ { 1 , … , m } ,
R true i ( ξ j ( i ) ) = { ∅ if the literal ν i occurs in C j , { ξ j ( i + 1 ) } otherwise , R_{\operatorname{true}_i}(\xi_j^{(i)})=
\begin{cases}
\varnothing& \text{if the literal }\nu_i\text{ occurs in }C_j,\\
\{\xi_j^{(i+1)}\} & \text{otherwise},
\end{cases} R true i ( ξ j ( i ) ) = { ∅ { ξ j ( i + 1 ) } if the literal ν i occurs in C j , otherwise ,
with R false i R_{\operatorname{false}_i} R false i defined in the same way using the literal ¬ ν i \lnot\nu_i ¬ ν i , and R t ( ξ j ( k + 1 ) ) = { ∗ } R_t(\xi_j^{(k+1)})=\{\ast\} R t ( ξ j ( k + 1 ) ) = { ∗ } for every j j j . The size of the construction is O ( k m ) O(km) O ( k m ) and it is computable in logarithmic space. The terminal modification t t t plays no role in the argument and is included for uniformity with the recoverability reduction of Appendix § 13 .
Every path from s 0 s_0 s 0 is a prefix of fan χ 1 ⋯ χ k t \operatorname{fan}\ \chi_1\cdots\chi_k t fan χ 1 ⋯ χ k t with each χ i ∈ { true i , false i } \chi_i\in\{\operatorname{true}_i,\operatorname{false}_i\} χ i ∈ { true i , false i } , and the choices χ 1 , … , χ k \chi_1,\ldots,\chi_k χ 1 , … , χ k encode an assignment θ \theta θ . By additivity and Proposition 11 , the lift L i + 1 L_{i+1} L i + 1 after fan χ 1 ⋯ χ i \operatorname{fan}\ \chi_1\cdots\chi_i fan χ 1 ⋯ χ i equals { ξ j ( i + 1 ) : C j is not satisfied by θ ( ν 1 ) , … , θ ( ν i ) } \{\xi_j^{(i+1)}: C_j\text{ is not satisfied by }\theta(\nu_1),\ldots,\theta(\nu_i)\} { ξ j ( i + 1 ) : C j is not satisfied by θ ( ν 1 ) , … , θ ( ν i )} , because the chain of ξ j \xi_j ξ j is cut exactly at the first layer whose chosen literal occurs in C j C_j C j , and chains of distinct clauses do not interact. In particular L 1 L_1 L 1 has m ≥ 1 m\ge1 m ≥ 1 elements, and L k + 1 = ∅ L_{k+1}=\varnothing L k + 1 = ∅ if and only if θ \theta θ satisfies every clause. The step t t t maps every element to ∗ \ast ∗ , so it cannot empty a nonempty lift.
If ϕ \phi ϕ is satisfiable, the path encoding a satisfying assignment has L k + 1 = ∅ L_{k+1}=\varnothing L k + 1 = ∅ , so γ 0 \gamma_0 γ 0 dies. Conversely, suppose γ 0 \gamma_0 γ 0 dies along some path. The lifts L 0 L_0 L 0 and L 1 L_1 L 1 are nonempty, and L k + 2 L_{k+2} L k + 2 is nonempty whenever L k + 1 L_{k+1} L k + 1 is, so the first empty lift is some L i L_i L i with 2 ≤ i ≤ k + 1 2\le i\le k+1 2 ≤ i ≤ k + 1 . The choices χ 1 , … , χ i − 1 \chi_1,\ldots,\chi_{i-1} χ 1 , … , χ i − 1 then satisfy every clause; extending them arbitrarily to ν i , … , ν k \nu_i,\ldots,\nu_k ν i , … , ν k gives a satisfying assignment of ϕ \phi ϕ . Hence death exists if and only if ϕ \phi ϕ is satisfiable.
PSPACE-hardness, general case. Reduce from NFA non-universality, which is PSPACE-complete [15 ] : given an NFA M = ( Q , Σ , μ , q 0 , Acc ) M=(Q,\Sigma,\mu,q_0,\operatorname{Acc}) M = ( Q , Σ , μ , q 0 , Acc ) , decide whether L ( M ) ≠ Σ ∗ \mathcal{L}(M)\ne\Sigma^* L ( M ) = Σ ∗ . The structure H H H has a state z z z with C ( z ) = Q \mathcal{C}(z)=Q C ( z ) = Q and γ 0 = q 0 \gamma_0=q_0 γ 0 = q 0 , a loop ℓ a : z → z \ell_a:z\to z ℓ a : z → z for each a ∈ Σ a\in\Sigma a ∈ Σ with R ℓ a ( q ) = μ ( q , a ) R_{\ell_a}(q)=\mu(q,a) R ℓ a ( q ) = μ ( q , a ) , and a terminal modification # : z → z t e r m \#:z\to z_{\mathrm{term}} # : z → z term with C ( z t e r m ) = { ∗ } \mathcal{C}(z_{\mathrm{term}})=\{\ast\} C ( z term ) = { ∗ } , R # ( q ) = { ∗ } R_{\#}(q)=\{\ast\} R # ( q ) = { ∗ } if q ∈ Acc q\in\operatorname{Acc} q ∈ Acc and R # ( q ) = ∅ R_{\#}(q)=\varnothing R # ( q ) = ∅ otherwise. A path from z z z is a word w = a 1 ⋯ a n w=a_1\cdots a_n w = a 1 ⋯ a n read by loops, optionally followed by # \# # . By Proposition 11 , the lift after reading w w w is the set μ ∗ ( q 0 , w ) \mu^*(q_0,w) μ ∗ ( q 0 , w ) of states reachable on w w w , and the lift after w # w\# w # is { ∗ } \{\ast\} { ∗ } if μ ∗ ( q 0 , w ) ∩ Acc ≠ ∅ \mu^*(q_0,w)\cap\operatorname{Acc}\ne\varnothing μ ∗ ( q 0 , w ) ∩ Acc = ∅ and ∅ \varnothing ∅ otherwise. The composite relation of a word is the relational composition of its letters’ relations, as functoriality requires.
If L ( M ) ≠ Σ ∗ \mathcal{L}(M)\ne\Sigma^* L ( M ) = Σ ∗ , take w ∉ L ( M ) w\notin\mathcal{L}(M) w ∈ / L ( M ) ; the path w # w\# w # gives an empty lift, so γ 0 \gamma_0 γ 0 dies. Conversely, suppose γ 0 \gamma_0 γ 0 dies along some path. The initial lift { q 0 } \{q_0\} { q 0 } is nonempty. If the lift is empty after reading a prefix w w w of the word, then μ ∗ ( q 0 , w ) = ∅ \mu^*(q_0,w)=\varnothing μ ∗ ( q 0 , w ) = ∅ , so w ∉ L ( M ) w\notin\mathcal{L}(M) w ∈ / L ( M ) . If it is empty after w # w\# w # , then μ ∗ ( q 0 , w ) ∩ Acc = ∅ \mu^*(q_0,w)\cap\operatorname{Acc}=\varnothing μ ∗ ( q 0 , w ) ∩ Acc = ∅ , so again w ∉ L ( M ) w\notin\mathcal{L}(M) w ∈ / L ( M ) . In either case L ( M ) ≠ Σ ∗ \mathcal{L}(M)\ne\Sigma^* L ( M ) = Σ ∗ . The construction has size O ( ∣ Q ∣ 2 ∣ Σ ∣ ) O(|Q|^2|\Sigma|) O ( ∣ Q ∣ 2 ∣Σ∣ ) and is computable in logarithmic space.
Complements. Death-freeness is the complement of death-existence, so it is coNP-complete for acyclic H H H . For general H H H it is PSPACE-complete, because PSPACE is closed under complement. □
Verifications for the Recover_avail Classification and Related Results
The acyclic reduction below is for the recoverability problem, not the death-existence problem of Appendix § 12 ; the two share the initial fan-out and variable-layer structure but differ in their fibers and terminal encodings.
This appendix provides the full technical derivations referred to from § 7.1 and from Proposition 7 and Remark 7 in § 7 . The instances below use the full-realization baseline of § 7 , so realized and stipulated lifts coincide and lineage death is read off the stipulated lifts L i ( γ 0 ) L_i(\gamma_0) L i ( γ 0 ) .
Overview. The two reductions are structurally similar to the death-existence reductions, with the key change that each clause (respectively, each NFA) is tracked as a pair of states: unsatisfied versus satisfied (respectively, not-yet-accepting versus accepting). The event set U ( ρ ) U(\rho) U ( ρ ) consists of the exclusion events generated when the recognition history excludes the initial tracked coordinates. Recover_avail then asks whether there exists an extension along which each excluded coordinate has an eligible descendant that is realized, undecided, and admissible for inscription. In the acyclic case, this reduces to CNF satisfiability: the pair-tracking encodes each clause’s satisfaction as a separate terminal reachability condition, and all conditions must be met along the same assignment-path. In the general case, this reduces to NFA-intersection-nonemptiness: the machines are simulated in parallel on a subset of their states over the same input word, and the terminal modification checks acceptance simultaneously for all machines. The full reductions, with the layer-by-layer indexing for the acyclic case and the parallel subset construction for the general case, are given in the subsections below.
The acyclic Recover_avail reduction in detail
We construct the structure H H H of Proposition 10 for the acyclic case.
States and modifications. Let ϕ = C 1 ∧ ⋯ ∧ C m \phi= C_1 \land\cdots\land C_m ϕ = C 1 ∧ ⋯ ∧ C m be a CNF formula with m ≥ 1 m \ge1 m ≥ 1 clauses over variables ν 1 , … , ν k \nu_1,\ldots,\nu_k ν 1 , … , ν k , k ≥ 1 k \ge1 k ≥ 1 . The structure H H H has states s 0 , s 1 , … , s k + 2 s_0,s_1,\ldots,s_{k+2} s 0 , s 1 , … , s k + 2 and no others, with modifications fan : s 0 → s 1 \operatorname{fan}:s_0 \to s_1 fan : s 0 → s 1 (fan-out), true i , false i : s i → s i + 1 \operatorname{true}_i,\operatorname{false}_i:s_i \to s_{i+1} true i , false i : s i → s i + 1 for i ∈ { 1 , … , k } i \in\{1,\ldots,k\} i ∈ { 1 , … , k } (variable choices), and t : s k + 1 → s k + 2 t:s_{k+1} \to s_{k+2} t : s k + 1 → s k + 2 (terminal). The composition condition is satisfied because the graph is acyclic and composite modifications are induced by relational composition of the one-step relations.
Fibers and relations. Let C ( s 0 ) = { γ 0 } C(s_0)=\{\gamma_0\} C ( s 0 ) = { γ 0 } . Let C ( s 1 ) = { ξ 1 ( 1 ) , … , ξ m ( 1 ) } C(s_1)=\{\xi_1^{(1)},\ldots,\xi_m^{(1)}\} C ( s 1 ) = { ξ 1 ( 1 ) , … , ξ m ( 1 ) } (one clause continuation per clause, tagged by layer 1). For i ∈ { 2 , … , k + 1 } i \in\{2,\ldots,k+1\} i ∈ { 2 , … , k + 1 } , let C ( s i ) = { uns j ( i ) , sat j ( i ) : j = 1 , … , m } C(s_i)=\{\operatorname{uns}_j^{(i)},\operatorname{sat}_j^{(i)}:j=1,\ldots,m\} C ( s i ) = { uns j ( i ) , sat j ( i ) : j = 1 , … , m } , where uns j ( i ) \operatorname{uns}_j^{(i)} uns j ( i ) denotes “clause C j C_j C j not yet satisfied at layer i i i ” and sat j ( i ) \operatorname{sat}_j^{(i)} sat j ( i ) denotes “clause C j C_j C j satisfied at layer i i i ”. Let C ( s k + 2 ) = { δ 1 , … , δ m } C(s_{k+2})=\{\delta_1,\ldots,\delta_m\} C ( s k + 2 ) = { δ 1 , … , δ m } .
The fan-out relation is R fan ( γ 0 ) = { ξ 1 ( 1 ) , … , ξ m ( 1 ) } R_{\operatorname{fan}}(\gamma_0)=\{\xi_1^{(1)},\ldots,\xi_m^{(1)}\} R fan ( γ 0 ) = { ξ 1 ( 1 ) , … , ξ m ( 1 ) } .
For each i ∈ { 1 , … , k } i \in\{1,\ldots,k\} i ∈ { 1 , … , k } , the relations at true i \operatorname{true}_i true i and false i \operatorname{false}_i false i act as follows. For each j ∈ { 1 , … , m } j \in\{1,\ldots,m\} j ∈ { 1 , … , m } :
For i = 1 i=1 i = 1 : R true 1 ( ξ j ( 1 ) ) = { sat j ( 2 ) } R_{\operatorname{true}_1}(\xi_j^{(1)})=\{\operatorname{sat}_j^{(2)}\} R true 1 ( ξ j ( 1 ) ) = { sat j ( 2 ) } if ν 1 = t r u e \nu_1=\mathrm{true} ν 1 = true satisfies clause C j C_j C j , and R true 1 ( ξ j ( 1 ) ) = { uns j ( 2 ) } R_{\operatorname{true}_1}(\xi_j^{(1)})=\{\operatorname{uns}_j^{(2)}\} R true 1 ( ξ j ( 1 ) ) = { uns j ( 2 ) } otherwise. Symmetrically for false 1 \operatorname{false}_1 false 1 .
For i ≥ 2 i \ge2 i ≥ 2 : R true i ( uns j ( i ) ) = { sat j ( i + 1 ) } R_{\operatorname{true}_i}(\operatorname{uns}_j^{(i)})=\{\operatorname{sat}_j^{(i+1)}\} R true i ( uns j ( i ) ) = { sat j ( i + 1 ) } if ν i = t r u e \nu_i=\mathrm{true} ν i = true satisfies C j C_j C j , and { uns j ( i + 1 ) } \{\operatorname{uns}_j^{(i+1)}\} { uns j ( i + 1 ) } otherwise; R true i ( sat j ( i ) ) = { sat j ( i + 1 ) } R_{\operatorname{true}_i}(\operatorname{sat}_j^{(i)})=\{\operatorname{sat}_j^{(i+1)}\} R true i ( sat j ( i ) ) = { sat j ( i + 1 ) } (once satisfied, stays satisfied). Symmetrically for false i \operatorname{false}_i false i .
In this construction a clause continuation survives when the clause is satisfied and is carried to ∅ \varnothing ∅ when it is not, so the surviving terminal continuations δ j \delta_j δ j correspond to the satisfied clauses. This is the encoding for the recoverability problem, where a path supplies witnesses for exactly the clauses satisfied along it; the death-existence reduction of Appendix § 12 uses the opposite polarity, carrying a continuation to ∅ \varnothing ∅ when the clause is satisfied.
The terminal modification is R t ( sat j ( k + 1 ) ) = { δ j } R_t(\operatorname{sat}_j^{(k+1)})=\{\delta_j\} R t ( sat j ( k + 1 ) ) = { δ j } and R t ( uns j ( k + 1 ) ) = ∅ R_t(\operatorname{uns}_j^{(k+1)})=\varnothing R t ( uns j ( k + 1 ) ) = ∅ .
Decision domain and criterion. Let I 0 = { γ 0 } I_0 = \{\gamma_0\} I 0 = { γ 0 } and D ( s 0 ) = { γ 0 } D(s_0) = \{\gamma_0\} D ( s 0 ) = { γ 0 } . Let D ( s 1 ) = C ( s 1 ) D(s_1) = C(s_1) D ( s 1 ) = C ( s 1 ) , and let S ( s 1 , ξ j ( 1 ) ) = excluded S(s_1,\xi_j^{(1)}) = \text{excluded} S ( s 1 , ξ j ( 1 ) ) = excluded for each j j j . Let D ( s k + 2 ) = { δ 1 , … , δ m } D(s_{k+2}) = \{\delta_1,\ldots,\delta_m\} D ( s k + 2 ) = { δ 1 , … , δ m } and S ( s k + 2 , δ j ) = inscribed S(s_{k+2},\delta_j) = \text{inscribed} S ( s k + 2 , δ j ) = inscribed for each j j j . Let D D D vanish at other states.
The recognition history. Fix the recognition history to exclude ξ j ( 1 ) \xi_j^{(1)} ξ j ( 1 ) at s 1 s_1 s 1 for every j j j (admissible because S S S so classifies them). This generates m m m unresolved exclusion events e 1 , … , e m e_1,\ldots,e_m e 1 , … , e m at the prefix ρ 1 \rho_1 ρ 1 ending at s 1 s_1 s 1 . So U ( ρ 1 ) = { e 1 , … , e m } U(\rho_1) = \{e_1,\ldots,e_m\} U ( ρ 1 ) = { e 1 , … , e m } .
The correspondence, forward direction. A path from s 0 s_0 s 0 to s k + 2 s_{k+2} s k + 2 is fan, then one choice per variable, then t t t . It encodes a total assignment θ \theta θ of ν 1 , … , ν k \nu_1,\ldots,\nu_k ν 1 , … , ν k . Suppose θ \theta θ satisfies every clause. Let p p p be the path that makes the choice matching θ \theta θ at each variable layer. Along p p p , the descendant of ξ j ( 1 ) \xi_j^{(1)} ξ j ( 1 ) at s k + 2 s_{k+2} s k + 2 is δ j \delta_j δ j : the clause continuation is carried through the layers sat j ( 2 ) , … , sat j ( k + 1 ) \operatorname{sat}_j^{(2)},\ldots,\operatorname{sat}_j^{(k+1)} sat j ( 2 ) , … , sat j ( k + 1 ) (because θ \theta θ satisfies C j C_j C j at the layer where the satisfying literal occurs, and once in sat \operatorname{sat} sat it stays there), and the terminal relation sends sat j ( k + 1 ) \operatorname{sat}_j^{(k+1)} sat j ( k + 1 ) to δ j \delta_j δ j . At the prefix η = p ∣ s k + 2 \eta= p|_{s_{k+2}} η = p ∣ s k + 2 , the state is s k + 2 s_{k+2} s k + 2 , the coordinate δ j \delta_j δ j has just entered the decision domain and is undecided, and S ^ ( s k + 2 , δ j ) = I \widehat{S}(s_{k+2},\delta_j) = \mathrm{I} S ( s k + 2 , δ j ) = I . So ( η , δ j ) (\eta,\delta_j) ( η , δ j ) is a corrective-route witness for e j e_j e j . Since this holds for every j j j , all m m m events have witnesses on the same extension, and Recover a v a i l ( ρ 1 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_1) Recover avail ( ρ 1 ) holds.
The correspondence, reverse direction. Suppose Recover a v a i l ( ρ 1 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_1) Recover avail ( ρ 1 ) holds. Then there is an extension ρ ′ ⪰ ρ 1 \rho' \succeq\rho_1 ρ ′ ⪰ ρ 1 and, for each j j j , a prefix η j \eta_j η j with ρ 1 ⪯ η j ⪯ ρ ′ \rho_1 \preceq\eta_j \preceq\rho' ρ 1 ⪯ η j ⪯ ρ ′ and a witness ( η j , δ ( j ) ) (\eta_j,\delta^{(j)}) ( η j , δ ( j ) ) for e j e_j e j ; the definition gives each event its own prefix, and we show that they coincide. The witness requires δ ( j ) ∈ R p j ( ξ j ( 1 ) ) ∩ D ( y j ) \delta^{(j)} \in R_{p_j}(\xi_j^{(1)}) \cap D(y_j) δ ( j ) ∈ R p j ( ξ j ( 1 ) ) ∩ D ( y j ) , where p j p_j p j is the segment of ρ ′ \rho' ρ ′ from s 1 s_1 s 1 to the state y j y_j y j at which η j \eta_j η j ends. Since D D D vanishes at every state except s 0 , s 1 , s k + 2 s_0,s_1,s_{k+2} s 0 , s 1 , s k + 2 , the candidates are y j ∈ { s 0 , s 1 , s k + 2 } y_j \in\{s_0,s_1,s_{k+2}\} y j ∈ { s 0 , s 1 , s k + 2 } . No modification enters s 0 s_0 s 0 , so y j ≠ s 0 y_j \ne s_0 y j = s 0 . The state s 1 s_1 s 1 is reached only at ρ 1 \rho_1 ρ 1 , the end of the given history, so the only candidate there is η j = ρ 1 \eta_j = \rho_1 η j = ρ 1 with the zero-length segment, for which R p j ( ξ j ( 1 ) ) ∩ D ( s 1 ) = { ξ j ( 1 ) } R_{p_j}(\xi_j^{(1)}) \cap D(s_1) = \{\xi_j^{(1)}\} R p j ( ξ j ( 1 ) ) ∩ D ( s 1 ) = { ξ j ( 1 ) } . That coordinate was decided E in ρ 1 \rho_1 ρ 1 , so B η j ( s 1 ) ( ξ j ( 1 ) ) ≠ U B_{\eta_j}(s_1)(\xi_j^{(1)}) \ne\mathrm{U} B η j ( s 1 ) ( ξ j ( 1 ) ) = U and S ^ = E ≠ I \widehat{S} = \mathrm{E} \ne\mathrm{I} S = E = I : it is not a witness. The graph is acyclic, so s k + 2 s_{k+2} s k + 2 is reached at most once, at the end of any extension. Hence y j = s k + 2 y_j = s_{k+2} y j = s k + 2 and η j \eta_j η j is the end of ρ ′ \rho' ρ ′ for every $j: the prefixes coincide, and every witness uses the same segment p p p of ρ ′ \rho' ρ ′ from s 1 s_1 s 1 to s k + 2 s_{k+2} s k + 2 . Moreover δ ( j ) ∈ C ( s k + 2 ) = { δ 1 , … , δ m } \delta^{(j)} \in C(s_{k+2}) = \{\delta_1,\ldots,\delta_m\} δ ( j ) ∈ C ( s k + 2 ) = { δ 1 , … , δ m } . Trace the relations: the only way for a clause continuation to reach any δ ℓ \delta_\ell δ ℓ is via the terminal relation t t t , which sends sat ℓ ( k + 1 ) \operatorname{sat}_\ell^{(k+1)} sat ℓ ( k + 1 ) to δ ℓ \delta_\ell δ ℓ ; the only way to reach sat ℓ ( k + 1 ) \operatorname{sat}_\ell^{(k+1)} sat ℓ ( k + 1 ) is by staying in the sat chain from the layer at which the clause first becomes satisfied. Hence δ ( j ) ∈ R p ( ξ j ( 1 ) ) \delta^{(j)} \in R_p(\xi_j^{(1)}) δ ( j ) ∈ R p ( ξ j ( 1 ) ) implies δ ( j ) = δ j \delta^{(j)} = \delta_j δ ( j ) = δ j and the path p p p satisfies C j C_j C j . This holds for every j j j , so the assignment θ \theta θ encoded by the variable choices along p p p satisfies every clause. Hence ϕ \phi ϕ is satisfiable. No alternative route can supply a witness for e j e_j e j : the only state where D D D is nonempty and a δ \delta δ -type coordinate is reachable is s k + 2 s_{k+2} s k + 2 , and the only relation producing δ j \delta_j δ j is t t t applied to sat j ( k + 1 ) \operatorname{sat}_j^{(k+1)} sat j ( k + 1 ) .
The only transition from the uns chain to the sat chain is at the layer where a selected literal satisfies that clause; no relation at any layer maps uns j ( i ) \operatorname{uns}_j^{(i)} uns j ( i ) directly to a sat coordinate of another clause, or to sat j ′ ( i ′ ) \operatorname{sat}_{j'}^{(i')} sat j ′ ( i ′ ) for i ′ > i + 1 i' > i + 1 i ′ > i + 1 . So a clause that has not been satisfied at any layer remains in the uns chain through every subsequent layer, and its terminal image under t t t is empty. A satisfied clause reaches exactly δ j \delta_j δ j .
Hence Recover a v a i l ( ρ 1 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_1) Recover avail ( ρ 1 ) holds iff there is an assignment θ \theta θ satisfying every clause, that is, iff ϕ \phi ϕ is satisfiable.
NP membership. A satisfying assignment is a certificate of polynomial size. Under the polynomial-time evaluation restriction stated in § 7.1 , verification takes polynomial time: propagate the clause continuations through the chosen assignment and check that every δ j \delta_j δ j is in the terminal lift, in D ( s k + 2 ) D(s_{k+2}) D ( s k + 2 ) , and satisfies S ^ ( s k + 2 , δ j ) = I \widehat{S}(s_{k+2},\delta_j)=\text{I} S ( s k + 2 , δ j ) = I . This completes the acyclic reduction.
The general Recover_avail reduction in detail
We construct the structure H H H of Proposition 10 for the general case, reducing from NFA-intersection-nonemptiness.
Input. Let A 1 , … , A k A_1,\ldots,A_k A 1 , … , A k be NFAs over a common alphabet Σ \Sigma Σ , with state sets Q 1 , … , Q k Q_1,\ldots,Q_k Q 1 , … , Q k , transition relations μ i : Q i × Σ → 2 Q i \mu_i: Q_i \times\Sigma\to2^{Q_i} μ i : Q i × Σ → 2 Q i , initial states q 0 , i q_{0,i} q 0 , i , and accepting sets Acc i \operatorname{Acc}_i Acc i . The question is whether ⋂ i = 1 k L ( A i ) ≠ ∅ \bigcap_{i=1}^{k} L(A_i) \ne\varnothing ⋂ i = 1 k L ( A i ) = ∅ . This problem is PSPACE-complete [14 ] .
States and fibers. The structure has states z 0 , z 1 , z 2 z_0,z_1,z_2 z 0 , z 1 , z 2 . Let C ( z 0 ) = { γ 0 } C(z_0)=\{\gamma_0\} C ( z 0 ) = { γ 0 } . Let C ( z 1 ) = Q 1 ⊔ ⋯ ⊔ Q k C(z_1)=Q_1\sqcup\cdots\sqcup Q_k C ( z 1 ) = Q 1 ⊔ ⋯ ⊔ Q k be the disjoint union of the state sets, with elements tagged by machine index so that blocks are disjoint. Let C ( z 2 ) = { A C C E P T 1 , … , A C C E P T k } C(z_2)=\{\mathrm{ACCEPT}_1,\ldots,\mathrm{ACCEPT}_k\} C ( z 2 ) = { ACCEPT 1 , … , ACCEPT k } .
Modifications. The fan-out modification fan : z 0 → z 1 \operatorname{fan}:z_0\to z_1 fan : z 0 → z 1 has R fan ( γ 0 ) = { q 0 , 1 , … , q 0 , k } R_{\operatorname{fan}}(\gamma_0)=\{q_{0,1},\ldots,q_{0,k}\} R fan ( γ 0 ) = { q 0 , 1 , … , q 0 , k } . For each a ∈ Σ a\in\Sigma a ∈ Σ , the loop modification ℓ a : z 1 → z 1 \ell_a:z_1\to z_1 ℓ a : z 1 → z 1 has R ℓ a ( q ) = μ i ( q , a ) R_{\ell_a}(q)=\mu_i(q,a) R ℓ a ( q ) = μ i ( q , a ) for q ∈ Q i q\in Q_i q ∈ Q i , block-wise. The terminal modification t : z 1 → z 2 t:z_1\to z_2 t : z 1 → z 2 has R t ( q ) = { A C C E P T i } R_t(q)=\{\mathrm{ACCEPT}_i\} R t ( q ) = { ACCEPT i } if q ∈ Acc i q\in\operatorname{Acc}_i q ∈ Acc i (with q ∈ Q i q\in Q_i q ∈ Q i ), and R t ( q ) = ∅ R_t(q)=\varnothing R t ( q ) = ∅ otherwise, again block-wise.
Composition condition. The composition of loop modifications ℓ a \ell_a ℓ a and ℓ b \ell_b ℓ b acts on z 1 z_1 z 1 ; R ℓ a ∘ ℓ b ( q ) R_{\ell_a\circ\ell_b}(q) R ℓ a ∘ ℓ b ( q ) for q ∈ Q i q\in Q_i q ∈ Q i equals R ℓ a ( R ℓ b ( q ) ) = μ i ( μ i ( q , b ) , a ) R_{\ell_a}(R_{\ell_b}(q))=\mu_i(\mu_i(q,b),a) R ℓ a ( R ℓ b ( q )) = μ i ( μ i ( q , b ) , a ) , which is the NFA transition for reading the two-letter word b a ba ba . Blocks remain disjoint, so composition holds block-wise. The composite t ∘ ℓ a t\circ\ell_a t ∘ ℓ a acts by R t ( R ℓ a ( q ) ) R_t(R_{\ell_a}(q)) R t ( R ℓ a ( q )) , matching the NFA transition followed by the terminal check. The empty set is absorbing under relational composition.
Decision domain and criterion. Let I 0 = { γ 0 } I_0=\{\gamma_0\} I 0 = { γ 0 } and D ( z 0 ) = { γ 0 } D(z_0)=\{\gamma_0\} D ( z 0 ) = { γ 0 } . Let D ( z 1 ) = { q 0 , 1 , … , q 0 , k } ⊊ C ( z 1 ) D(z_1)=\{q_{0,1},\ldots,q_{0,k}\}\subsetneq C(z_1) D ( z 1 ) = { q 0 , 1 , … , q 0 , k } ⊊ C ( z 1 ) , and let S ( z 1 , q 0 , i ) = excluded S(z_1,q_{0,i})=\text{excluded} S ( z 1 , q 0 , i ) = excluded for each i i i . Let D ( z 2 ) = { A C C E P T 1 , … , A C C E P T k } D(z_2)=\{\mathrm{ACCEPT}_1,\ldots,\mathrm{ACCEPT}_k\} D ( z 2 ) = { ACCEPT 1 , … , ACCEPT k } and S ( z 2 , A C C E P T i ) = inscribed S(z_2,\mathrm{ACCEPT}_i)=\text{inscribed} S ( z 2 , ACCEPT i ) = inscribed for each i i i . Let D D D vanish at other states.
The recognition history. Fix the recognition history to exclude q 0 , i q_{0,i} q 0 , i at z 1 z_1 z 1 for every i i i (admissible because S S S so classifies them). This generates k k k unresolved exclusion events e 1 , … , e k e_1,\ldots,e_k e 1 , … , e k at the prefix ρ 1 \rho_1 ρ 1 ending at z 1 z_1 z 1 . So U ( ρ 1 ) = { e 1 , … , e k } U(\rho_1)=\{e_1,\ldots,e_k\} U ( ρ 1 ) = { e 1 , … , e k } .
The correspondence, forward direction. A path from z 0 z_0 z 0 to z 2 z_2 z 2 is fan, then a finite sequence of loop modifications ℓ a 1 , … , ℓ a n \ell_{a_1},\ldots,\ell_{a_n} ℓ a 1 , … , ℓ a n (possibly empty, corresponding to the empty word), then t t t . It encodes a word w = a 1 ⋯ a n ∈ Σ ∗ w=a_1\cdots a_n\in\Sigma^* w = a 1 ⋯ a n ∈ Σ ∗ .
Suppose w ∈ ⋂ i L ( A i ) w\in\bigcap_i L(A_i) w ∈ ⋂ i L ( A i ) . For each i i i , the lift of q 0 , i q_{0,i} q 0 , i after reading w w w is μ i ∗ ( q 0 , i , w ) \mu_i^*(q_{0,i},w) μ i ∗ ( q 0 , i , w ) , which contains some state in Acc i \operatorname{Acc}_i Acc i (since w ∈ L ( A i ) w\in L(A_i) w ∈ L ( A i ) ). The terminal relation sends that state to A C C E P T i \mathrm{ACCEPT}_i ACCEPT i , so A C C E P T i ∈ R t ( μ i ∗ ( q 0 , i , w ) ) \mathrm{ACCEPT}_i\in R_t(\mu_i^*(q_{0,i},w)) ACCEPT i ∈ R t ( μ i ∗ ( q 0 , i , w )) . At the prefix η = p ∣ z 2 \eta=p|_{z_2} η = p ∣ z 2 , the state is z 2 z_2 z 2 , the coordinate A C C E P T i \mathrm{ACCEPT}_i ACCEPT i has just entered the decision domain and is undecided, and S ^ ( z 2 , A C C E P T i ) = I \widehat{S}(z_2,\mathrm{ACCEPT}_i)=\text{I} S ( z 2 , ACCEPT i ) = I . So ( η , A C C E P T i ) (\eta,\mathrm{ACCEPT}_i) ( η , ACCEPT i ) is a corrective-rout witness for e i e_i e i . Since this holds for every i i i , all k k k events have witnesses on the same extension, and Recover_avail( ρ 1 ) (\rho_1) ( ρ 1 ) holds.
The construction is a parallel subset simulation of the k k k machines on the same word, not a product of their individual states. The fiber C ( z 1 ) = Q 1 ⊔ ⋯ ⊔ Q k C(z_1)=Q_1\sqcup\cdots\sqcup Q_k C ( z 1 ) = Q 1 ⊔ ⋯ ⊔ Q k is the disjoint union of the state sets, and the fan-out R fan ( γ 0 ) = { q 0 , 1 , … , q 0 , k } R_{\operatorname{fan}}(\gamma_0)=\{q_{0,1},\ldots,q_{0,k}\} R fan ( γ 0 ) = { q 0 , 1 , … , q 0 , k } places the initial state of every machine in the lift simultaneously. The loop modifications act block-wise, and the transition relation μ i \mu_i μ i set-valued, so at each step the lift is a subset of the disjoint union containing a subset of each block. For the path p p p that encodes w w w ,
R p ( { q 0 , i } ) = μ i ∗ ( q 0 , i , w ) , R_p(\{q_{0,i}\}) = \mu_i^*(q_{0,i},w), R p ({ q 0 , i }) = μ i ∗ ( q 0 , i , w ) ,
the full set of states reachable by A i A_i A i on w w w ; the machine may be in several states at once, or in none, and the lift tracks all of them simultaneously.
The terminal modification t : z 1 → z 2 t:z_1 \to z_2 t : z 1 → z 2 maps every accepting state in block i i i to A C C E P T i \mathrm{ACCEPT}_i ACCEPT i and every non-accepting state to ∅ \varnothing ∅ . Hence
A C C E P T i ∈ R t ( R p ( { q 0 , i } ) ) ⟺ μ i ∗ ( q 0 , i , w ) ∩ A c c i ≠ ∅ ⟺ w ∈ L ( A i ) . \mathrm{ACCEPT}_i \in R_t(R_p(\{q_{0,i}\})) \Longleftrightarrow\mu_i^*(q_{0,i},w) \cap\mathrm{Acc}_i \ne\varnothing\Longleftrightarrow w \in\mathcal{L}(A_i). ACCEPT i ∈ R t ( R p ({ q 0 , i })) ⟺ μ i ∗ ( q 0 , i , w ) ∩ Acc i = ∅ ⟺ w ∈ L ( A i ) .
Therefore e i e_i e i has a witness on this path iff w ∈ L ( A i ) w \in\mathcal{L}(A_i) w ∈ L ( A i ) , and all exclusion events have witnesses on the same path exactly when some word is accepted by every A i A_i A i .
The correspondence, reverse direction. Conversely, suppose Recover a v a i l ( ρ 1 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_1) Recover avail ( ρ 1 ) holds. Then there is an extension ρ ′ ⪰ ρ 1 \rho' \succeq\rho_1 ρ ′ ⪰ ρ 1 and, for each i i i , a prefix η i \eta_i η i with ρ 1 ⪯ η i ⪯ ρ ′ \rho_1 \preceq\eta_i \preceq\rho' ρ 1 ⪯ η i ⪯ ρ ′ and a witness ( η i , δ ( i ) ) (\eta_i,\delta^{(i)}) ( η i , δ ( i ) ) for e i e_i e i ; the definition gives each event its own prefix, and we show below that they coincide. The witness requires δ ( i ) ∈ R p i ( { q 0 , i } ) ∩ D ( y i ) \delta^{(i)} \in R_{p_i}(\{q_{0,i}\}) \cap D(y_i) δ ( i ) ∈ R p i ({ q 0 , i }) ∩ D ( y i ) where p i p_i p i is the segment of ρ ′ \rho' ρ ′ from z 1 z_1 z 1 to the state y i y_i y i at which η i \eta_i η i ends.
Since D D D vanishes at every state except z 0 , z 1 , z 2 z_0,z_1,z_2 z 0 , z 1 , z 2 , the candidates are y i ∈ { z 0 , z 1 , z 2 } y_i \in\{z_0,z_1,z_2\} y i ∈ { z 0 , z 1 , z 2 } . No modification enters z 0 z_0 z 0 , so y i ≠ z 0 y_i \ne z_0 y i = z 0 . The state z 1 z_1 z 1 is revisited by the loops ℓ a \ell_a ℓ a , so it is not excluded by position; it is excluded by the data. The loops and R f a n R_{\mathrm{fan}} R fan act block-wise, so R p i ( { q 0 , i } ) ⊆ Q i R_{p_i}(\{q_{0,i}\}) \subseteq Q_i R p i ({ q 0 , i }) ⊆ Q i , and D ( z 1 ) ∩ Q i = { q 0 , i } D(z_1) \cap Q_i = \{q_{0,i}\} D ( z 1 ) ∩ Q i = { q 0 , i } . The only possible witness at z 1 z_1 z 1 is therefore the coordinate q 0 , i q_{0,i} q 0 , i itself, whether at η i = ρ 1 \eta_i=\rho_1 η i = ρ 1 (zero-length segment) or after some loops, which has B = E B=E B = E from ρ 1 \rho_1 ρ 1 (no transition alters a completed coordinate) and S ^ = E ≠ I \widehat{S}=E\ne I S = E = I ; it is not undecided and not admissible for inscription. Hence y i = z 2 y_i=z_2 y i = z 2 and δ ( i ) ∈ C ( z 2 ) = { A C C E P T 1 , … , A C C E P T k } \delta^{(i)} \in C(z_2)=\{\mathrm{ACCEPT}_1,\ldots,\mathrm{ACCEPT}_k\} δ ( i ) ∈ C ( z 2 ) = { ACCEPT 1 , … , ACCEPT k } . Since ρ ′ \rho' ρ ′ reaches z 2 z_2 z 2 at most once and no modification leaves z 2 z_2 z 2 , the state z 2 z_2 z 2 is reached only at the end of ρ ′ \rho' ρ ′ , so all η i \eta_i η i coincide with it and every witness uses the same segment p p p of ρ ′ \rho' ρ ′ from z 1 z_1 z 1 to z 2 z_2 z 2 .
From z 1 z_1 z 1 , the only modifications available are the loops ℓ a \ell_a ℓ a and the terminal t : z 1 → z 2 t:z_1\to z_2 t : z 1 → z 2 . A path from z 1 z_1 z 1 to z 2 z_2 z 2 is therefore a finite sequence of loop modifications followed by t t t , i.e.,
p = t ∘ ℓ a n ∘ ⋯ ∘ ℓ a 1 p = t \circ\ell_{a_n} \circ\cdots\circ\ell_{a_1} p = t ∘ ℓ a n ∘ ⋯ ∘ ℓ a 1
for some word w = a 1 ⋯ a n w=a_1\cdots a_n w = a 1 ⋯ a n .
Then
R p ( { q 0 , i } ) = R t ( R ℓ a n ∘ ⋯ ∘ ℓ a 1 ( { q 0 , i } ) ) = R t ( μ i ∗ ( q 0 , i , w ) ) , R_p(\{q_{0,i}\}) = R_t(R_{\ell_{a_n}\circ\cdots\circ\ell_{a_1}}(\{q_{0,i}\})) = R_t(\mu_i^*(q_{0,i},w)), R p ({ q 0 , i }) = R t ( R ℓ a n ∘ ⋯ ∘ ℓ a 1 ({ q 0 , i })) = R t ( μ i ∗ ( q 0 , i , w )) ,
which is { A C C E P T i } \{\mathrm{ACCEPT}_i\} { ACCEPT i } if μ i ∗ ( q 0 , i , w ) ∩ A c c i ≠ ∅ \mu_i^*(q_{0,i},w)\cap\mathrm{Acc}_i\ne\varnothing μ i ∗ ( q 0 , i , w ) ∩ Acc i = ∅ and ∅ \varnothing ∅ otherwise. So a witness for e i e_i e i exists iff w ∈ L ( A i ) w\in\mathcal{L}(A_i) w ∈ L ( A i ) . The segment p p p is common to all events, as shown above, and encodes a single word w w w . Hence a single word w w w is accepted by every A i A_i A i .
No other terminal coordinate can witness event e i e_i e i : the terminal relation is block-wise, so for q ∈ Q i q\in Q_i q ∈ Q i the image R t ( q ) R_t(q) R t ( q ) is either { A C C E P T i } \{\mathrm{ACCEPT}_i\} { ACCEPT i } or ∅ \varnothing ∅ , never a terminal coordinate of another block. The witness must use the same extension and hence the same word for every event.
Hence Recover a v a i l ( ρ 1 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_1) Recover avail ( ρ 1 ) holds iff ⋂ i L ( A i ) ≠ ∅ \bigcap_i \mathcal{L}(A_i)\ne\varnothing ⋂ i L ( A i ) = ∅ .
PSPACE membership. The argument is given for the restricted, state-determined model of Section § 7.1 : the determination rule Δ \Delta Δ is a function of the state reached alone, and is evaluable in space polynomial in the extensional input. Let ρ \rho ρ be the given history. The search is written directly from Eq. (26) , which asks for one extension ρ ′ \rho' ρ ′ that is death-free and gives every event of U ( ρ ) U(\rho) U ( ρ ) a witness.
Fixed data. The recognition state B ρ B_\rho B ρ , the set U ( ρ ) U(\rho) U ( ρ ) with the excluded coordinate γ e \gamma_e γ e and state x e x_e x e of each event, and I 0 I_0 I 0 are computed from ρ \rho ρ and do not change during the search. If U ( ρ ) U(\rho) U ( ρ ) contains a lineage-death event, the instance is rejected, since such an event has no witness.
Configuration. A configuration is c = ( y , ( L e ) e ∈ U ( ρ ) , ( M γ ) γ ∈ I 0 , ( b e ) e ∈ U ( ρ ) ) c=(y,(L_e)_{e\in U(\rho)},(M_\gamma)_{\gamma\in I_0},(b_e)_{e\in U(\rho)}) c = ( y , ( L e ) e ∈ U ( ρ ) , ( M γ ) γ ∈ I 0 , ( b e ) e ∈ U ( ρ ) ) : the current state y y y of the walk; for each unresolved event e e e , the lift L e = R p ( γ e ) ⊆ C ( y ) L_e=R_p(\gamma_e)\subseteq C(y) L e = R p ( γ e ) ⊆ C ( y ) along the segment p : x e ⇝ y p:x_e\leadsto y p : x e ⇝ y of the walk so far; for each γ ∈ I 0 \gamma\in I_0 γ ∈ I 0 , its current lift M γ ⊆ C ( y ) M_\gamma\subseteq C(y) M γ ⊆ C ( y ) ; and one bit $b_e per event, indexed by the event, recording whether a witness for e e e has been found. The initial configuration is computed from ρ \rho ρ . A configuration has size O ( ( ∣ U ( ρ ) ∣ + ∣ I 0 ∣ ) ⋅ m + ∣ U ( ρ ) ∣ + log ∣ X ∣ ) O((|U(\rho)|+|I_0|)\cdot m+|U(\rho)|+\log|X|) O (( ∣ U ( ρ ) ∣ + ∣ I 0 ∣ ) ⋅ m + ∣ U ( ρ ) ∣ + log ∣ X ∣ ) bits, where m m m is the largest fiber, which is polynomial in the input.
Transition. A step chooses a modification f : y → y ′ f:y\to y' f : y → y ′ and replaces every L e L_e L e and M γ 0 M_{\gamma_0} M γ 0 by its image under R f R_f R f , computed with Δ \Delta Δ ; all events thus advance along the same walk. It then sets b e : = 1 b_e:=1 b e := 1 if b e = 1 b_e=1 b e = 1 already, or if some δ ∈ L e ∩ D ( y ′ ) \delta\in L_e\cap D(y') δ ∈ L e ∩ D ( y ′ ) has S ^ ( y ′ , δ ) = I \widehat{S}(y',\delta)=\mathrm{I} S ( y ′ , δ ) = I and is undecided at the current prefix. The same test is applied once to the initial configuration, for η = ρ \eta=\rho η = ρ .
Acceptance. Accept at the first configuration in which every b e = 1 b_e=1 b e = 1 , provided no M γ 0 M_{\gamma_0} M γ 0 has been empty at any configuration so far.
Each clause of Eq. (26) is carried by one feature of this search. Common extension : there is one walk, and every L e L_e L e is updated by every step; the bits are indexed by event, so each event may be witnessed at its own prefix of that walk, as the definition allows. Death-freeness : the definition asks for no death event in F ( ρ ′ ) F(\rho') F ( ρ ′ ) , which also excludes a witness that is followed by a later death. If ρ ′ \rho' ρ ′ is a witnessing extension, its truncation at the last witnessing prefix is also one: each witness depends only on the history up to its prefix η \eta η , and F F F is monotone, so truncation cannot introduce a death event. The search stops at the first configuration with every bit set, which is that truncation, so checking for death up to that point suffices. Undecidedness at the witness prefix : the condition B η ( y ) ( δ ) = U B_\eta(y)(\delta)=\mathrm{U} B η ( y ) ( δ ) = U is evaluated at the prefix η \eta η at which the witness is found. A recognition event beyond ρ \rho ρ replaces U \mathrm{U} U by a value and so cannot create a witness; it is enough to search extensions with no such events. For a coordinate at a state reached by ρ \rho ρ , the value at η \eta η is then its value in B ρ B_\rho B ρ , and a coordinate first reached beyond ρ \rho ρ is initialized to U \mathrm{U} U . The test above therefore reads only the fixed table B ρ B_\rho B ρ .
The number of configurations is at most ∣ X ∣ ⋅ 2 ( ∣ U ( ρ ) ∣ + ∣ I 0 ∣ ) m ⋅ 2 ∣ U ( ρ ) ∣ |X|\cdot2^{(|U(\rho)|+|I_0|)m}\cdot2^{|U(\rho)|} ∣ X ∣ ⋅ 2 ( ∣ U ( ρ ) ∣ + ∣ I 0 ∣ ) m ⋅ 2 ∣ U ( ρ ) ∣ , exponential in the input. A walk that revisits a configuration can be shortened by deleting the loop, which loses no witness bit, since equal configurations carry equal bits. A nondeterministic machine can therefore guess the walk one modification at a time, storing only the current configuration and a step counter bounded by the number of configurations, which takes polynomial space. Evaluating Δ \Delta Δ at each step uses polynomial space, so the weaker polynomial-space assumption suffices for membership; the polynomial-time assumption is needed only for the acyclic NP upper bound. The problem is in NPSPACE, and by Savitch’s theorem [16 ] NPSPACE = PSPACE, so R e c o v e r a v a i l \mathrm{Recover}_{\mathrm{avail}} Recover avail is in PSPACE under the restricted model.
Death-freeness is part of the configuration above, through the lifts M γ 0 M_{\gamma_0} M γ 0 . The reductions are unaffected; see the death-freeness observation at the end of this subsection.
On the two evaluability assumptions. The acyclic reduction uses the polynomial-time evaluability of Δ \Delta Δ to verify a path certificate: the certificate is the path, and the verifier computes the lift step by step, applying Δ \Delta Δ once per step. The general reduction uses only polynomial-space evaluability, because the certificate is a walk with a counter and the verifier simulates the walk rather than outputting it. The two assumptions are not different in kind; they are the same requirement at different strengths, and the choice is dictated by the certificate type. A path certificate could also be verified by simulation, which would weaken the acyclic bound to PSPACE without changing the result, since NP is contained in PSPACE. The stronger assumption is stated for the acyclic case because the NP bound is the sharp one for that case, and the sharp bound requires the certificate to be checkable in polynomial time.
Death-freeness of the witnessing extensions. The death-freeness conjunct of Eq. (26) is satisfied automatically along the witnessing extension in both reductions. In each, every excluded coordinate is a direct image of γ 0 \gamma_0 γ 0 under the fan-out ( ξ j ( 1 ) , (\xi_j^{(1)}, ( ξ j ( 1 ) , respectively q 0 , i ) q_{0,i}) q 0 , i ) ; a witness for it lies in R ρ R_\rho R ρ of that coordinate and so in the lift of γ 0 \gamma_0 γ 0 at the terminal state ( s k + 2 , (s_{k+2}, ( s k + 2 , respectively z 2 ) z_2) z 2 ) , where ρ ′ \rho' ρ ′ ends; and a lift that is empty at some stage is empty at every later stage, so L i ( γ 0 ) ≠ ∅ L_i(\gamma_0)\ne\varnothing L i ( γ 0 ) = ∅ at every stage of ρ ′ \rho' ρ ′ . The observation is used in the forward directions and in the membership arguments, where the configuration tracks the lift of γ 0 \gamma_0 γ 0 ; the reverse directions use only the witness. It is specific to these constructions: in a general instance an excluded coordinate need not descend from γ 0 \gamma_0 γ 0 , and a witnessing extension need not be death-free.
Verification of the availability versus trace proposition
Positive direction (strong fairness). Suppose the structure has finitely many coordinates, the recognition history is strongly fair, τ \tau τ contains no lineage-death event, and for each exclusion event e ∈ F ( τ ) e \in F(\tau) e ∈ F ( τ ) a witness for e e e keeps occurring along τ \tau τ for as long as e e e is unresolved. Fix e e e and suppose, for contradiction, that e e e is never resolved: e ∈ U ( τ ∣ i ) e \in U(\tau|i) e ∈ U ( τ ∣ i ) for all i ≥ i 0 i \ge i_0 i ≥ i 0 . By hypothesis, for every i ≥ i 0 i \ge i_0 i ≥ i 0 there are j ≥ i j \ge i j ≥ i and a witness ( τ ∣ j , δ j ) (\tau|j,\delta_j) ( τ ∣ j , δ j ) for e e e , ending at a state y j y_j y j . Since there are finitely many coordinates, some coordinate ( y , δ ) (y,\delta) ( y , δ ) is the witness coordinate at infinitely many j j j . At each such τ ∣ j \tau|j τ ∣ j the coordinate is undecided, and a completed coordinate is never altered, so it is undecided at every prefix of τ \tau τ . At each such j j j the transition U → I \mathrm{U} \to\mathrm{I} U → I at ( y , δ ) (y,\delta) ( y , δ ) is admissible: the witness gives δ ∈ R p ( γ ) ∩ D ( y ) \delta\in R_p(\gamma) \cap D(y) δ ∈ R p ( γ ) ∩ D ( y ) , B = U B = \mathrm{U} B = U and S ^ ( y , δ ) = I \widehat{S}(y,\delta) = \mathrm{I} S ( y , δ ) = I . The transition is thus admissible infinitely often, so by strong fairness it is eventually taken, and the coordinate is then no longer undecided, contrary to the previous sentence. Hence e e e is resolved. Since e e e was arbitrary and τ \tau τ contains no death event, Recover t r a c e ( τ ) \operatorname{Recover}_{\mathrm{trace}}(\tau) Recover trace ( τ ) holds. The hypothesis requires a cycle through the opportunity state, so this direction never applies to acyclic structures, where every history is finite. The hypothesis is stated for as long as e e e is unresolved, and not as infinite recurrence outright, because a witness requires the coordinate to be undecided: on a strongly fair history a witness cannot recur infinitely often, since fairness forces the transition and ends the opportunity.
Negative direction. We construct the infinite history τ \tau τ of Proposition 7 .
Setup. Fix a finite structure H H H containing a state y y y with the following property: at y y y there is a cycle ℓ : y → y \ell: y \to y ℓ : y → y with R ℓ ( δ ) = { δ } R_\ell(\delta) = \{\delta\} R ℓ ( δ ) = { δ } for some δ ∈ C ( y ) \delta\in C(y) δ ∈ C ( y ) , and δ \delta δ is a structurally eligible descendant of a coordinate γ \gamma γ that has been excluded at an earlier prefix. Suppose δ \delta δ also satisfies δ ∈ D ( y ) \delta\in D(y) δ ∈ D ( y ) and S ^ ( y , δ ) = I \widehat{S}(y,\delta) = \mathrm{I} S ( y , δ ) = I . Write e = ( ρ e , γ ) e = (\rho_e,\gamma) e = ( ρ e , γ ) for the exclusion event of γ \gamma γ at a state x x x that τ \tau τ visits before its first arrival at y y y , and suppose e e e is the only failure event generated along τ \tau τ (in particular, no lineage-death event occurs).
The infinite history. Let τ \tau τ be the infinite history that, from some point on, revisits y y y by applying ℓ \ell ℓ at each step. Let the recognition history never perform the transition U → I \mathrm{U} \to\mathrm{I} U → I at ( y , δ ) (y,\delta) ( y , δ ) , though the transition is admissible at every visit.
Availability at every prefix. Fix any finite prefix τ ∣ i \tau|i τ ∣ i of τ \tau τ . Since τ \tau τ revisits y y y infinitely often, there is j ≥ i j \ge i j ≥ i such that τ ∣ j \tau|j τ ∣ j ends at y y y . Take ρ ′ = η = τ ∣ j \rho' = \eta= \tau|j ρ ′ = η = τ ∣ j . The segment ρ \rho ρ from the state x x x of the exclusion to y y y along τ ∣ j \tau|j τ ∣ j carries δ \delta δ in R p ( γ ) R_p(\gamma) R p ( γ ) : δ \delta δ is a structurally eligible descendant at the first arrival at y y y , and each further application of ℓ \ell ℓ preserves it because R ℓ ( δ ) = { δ } R_\ell(\delta) = \{\delta\} R ℓ ( δ ) = { δ } . No modification out of y y y is needed, since the witness sits at y y y itself. Because the recognition history never performs the transition at ( y , δ ) (y,\delta) ( y , δ ) , the pair ( η , δ ) (\eta,\delta) ( η , δ ) satisfies
δ ∈ R p ( γ ) ∩ D ( y ) , B η ( y ) ( δ ) = U , S ^ ( y , δ ) = I , \delta\in R_p(\gamma) \cap D(y), \qquad B_\eta(y)(\delta) = \mathrm{U}, \qquad\widehat{S}(y,\delta) = \mathrm{I}, δ ∈ R p ( γ ) ∩ D ( y ) , B η ( y ) ( δ ) = U , S ( y , δ ) = I ,
so it is a corrective-route witness for e e e . Hence W e ( ρ ′ ) ≠ ∅ W_e(\rho') \ne\varnothing W e ( ρ ′ ) = ∅ , and Recover a v a i l ( τ ∣ i ) \operatorname{Recover}_{\mathrm{avail}}(\tau|i) Recover avail ( τ ∣ i ) holds.
Trace failure. Under the stipulated recognition history, the transition U → I \mathrm{U} \to\mathrm{I} U → I at ( y , δ ) (y,\delta) ( y , δ ) is never performed. So for every prefix τ ∣ i \tau|i τ ∣ i with e ∈ F ( τ ∣ i ) e \in F(\tau|i) e ∈ F ( τ ∣ i ) , also e ∈ U ( τ ∣ i ) e \in U(\tau|i) e ∈ U ( τ ∣ i ) . Hence Recover t r a c e ( τ ) \operatorname{Recover}_{\mathrm{trace}}(\tau) Recover trace ( τ ) fails, because e e e never leaves U U U .
Consequence. The predicate Recover a v a i l \operatorname{Recover}_{\mathrm{avail}} Recover avail can hold at every finite prefix of an infinite history while Recover t r a c e \operatorname{Recover}_{\mathrm{trace}} Recover trace fails on that same history. The failure is not epistemic — it is a consequence of the framework’s separation of admissibility from occurrence, and with a strongly fair recognition history it does not arise.
Verification of the constructed asymmetry in Remark 7
Assume the structure contains neutral modifications that can be repeated indefinitely. We construct the two infinite extensions used in the remark.
Fix a finite prefix ρ \rho ρ ending with an unresolved exclusion event e = ( ρ e , γ ) e=(\rho_e,\gamma) e = ( ρ e , γ ) . Suppose γ \gamma γ has a structurally eligible descendant δ \delta δ at a state y y y reachable from the end of ρ \rho ρ by a finite path p p p , with δ ∈ D ( y ) \delta\in D(y) δ ∈ D ( y ) and S ^ ( y , δ ) = I \widehat{S}(y,\delta)=\mathord{\mathrm{I}} S ( y , δ ) = I .
Neutral extensions. Let n ≥ 1 n\ge1 n ≥ 1 . From ρ \rho ρ , extend by n n n neutral modifications that do not affect the structural image of γ \gamma γ or the structure of p p p ; that is, they are modifications on states disjoint from y y y and from the path p p p , or self-loops on states whose fibers do not carry γ \gamma γ -descendants. Let ρ + n \rho^{+n} ρ + n denote the resulting prefix of length n n n beyond ρ \rho ρ .
Two extensions. From ρ + n \rho^{+n} ρ + n , define:
τ 1 \tau_1 τ 1 : extend by the path p p p to y y y , and at y y y realize and inscribe δ \delta δ . Then e e e is resolved on τ 1 \tau_1 τ 1 .
τ 2 \tau_2 τ 2 : extend by a modification whose relation carries the image of γ \gamma γ to ∅ \varnothing ∅ on every branch from the current state, and then by any further modifications. Then e e e is never resolved on τ 2 \tau_2 τ 2 .
Prefix-indistinguishability. Since both τ 1 \tau_1 τ 1 and τ 2 \tau_2 τ 2 agree with ρ + n \rho^{+n} ρ + n on the first n n n steps beyond ρ \rho ρ , and n n n is arbitrary, no finite prefix of ρ \rho ρ determines whether e e e is eventually resolved. This establishes the asymmetry claimed in the remark.
Realization
The abstract model of § 6 gives a stipulated structure. This appendix adds conformance determination: which of its continuations are found to be realized, distinguishing non-realization from a realized continuation that is set aside.
Realization is history-indexed. The stipulated continuation structure is fixed: C ( x ) C(x) C ( x ) and R f R_f R f depend on the state and the modification but not on the history by which the state was reached. Realization is not: the realized subset C ρ r ( x ) C_\rho^{r}(x) C ρ r ( x ) is attached to the pair ( x , ρ ) (x,\rho) ( x , ρ ) —a state together with the finite history reaching it—because the conformance evidence available at the end of a history may depend on the history, not merely on the state. The same structural state can therefore have different realized subsets on different histories. The recoverability predicates of § 7 respect this indexing by quantifying over extensions of a given history. The complexity results of § 7.1 are stated for a restricted model in which Δ \Delta Δ is state-determined and effectively evaluable; the general definition above permits history-indexed realization, which is not covered by those results.
Setting
For a system without explicit compositional structure, the pair ( C , R ) (C,R) ( C , R ) is stipulated . Stipulation is a governance act. Three things are separated: a structural fact is a consequence of the stipulation; a conformance determination records which stipulated continuations the system realizes; a recognition record operation inscribes or excludes. The first is formal. The second and third are accountable acts and are recorded as such.
In this appendix, we use the abbreviation C i r e = C ρ r e ( x i ) C_i^{\mathrm{re}} = C_{\rho}^{\mathrm{re}}(x_i) C i re = C ρ re ( x i ) for the realized subset at stage i i i of the realized history ρ \rho ρ . A recognition record is realized if it additionally satisfies
I ( x ) ⊆ D ρ r e ( x ) ⊆ C i r e ⊆ C ( x ) I(x) \subseteq D_{\rho}^{\mathrm{re}}(x) \subseteq C_i^{\mathrm{re}} \subseteq C(x) I ( x ) ⊆ D ρ re ( x ) ⊆ C i re ⊆ C ( x )
at each realized coordinate, with D ρ r e ( x ) = D ( x ) ∩ C i r e D_{\rho}^{\mathrm{re}}(x) = D(x) \cap C_i^{\mathrm{re}} D ρ re ( x ) = D ( x ) ∩ C i re . The main recognition record of § 4 is defined only by I ( x ) ⊆ D ( x ) I(x) \subseteq D(x) I ( x ) ⊆ D ( x ) . The realized condition applies when recognition is restricted to realized continuations, which is the case of interest in this section. If every continuation is realized, the chain reduces to I ( x ) ⊆ D ( x ) ⊆ C ( x ) I(x) \subseteq D(x) \subseteq C(x) I ( x ) ⊆ D ( x ) ⊆ C ( x ) .
Non-realization as the encoding of feature loss. A failed transformation and a non-realized continuation are different events. A failed transformation may prevent the successor state from being reached at all, whereas a non-realized continuation presupposes that a state and its continuation space are available for determination. The realization-cut analysis assumes that the relevant history and its state layers have been specified, and represents loss of a continuation by non-realization of the corresponding vertex in the path graph. Failures that prevent the history itself from proceeding require a different encoding and lie outside the graph model developed in this appendix. The realization-cut number introduced below measures robustness against non-realization within a stipulated path graph.
Determinations can be revised. The determination rule Δ \Delta Δ is fixed within a single analysis. A later determination may revise an earlier one, for example when new conformance evidence becomes available. The framework treats determinations as fixed for the duration of an analysis; a revision would be modeled by re-running the analysis with a different Δ \Delta Δ and recording the change as a new determination. The framework records determinations and their provenance; it does not adjudicate between competing determinations.
Realized subsets and realized lifts
Fix a determination rule Δ \Delta Δ whose input is a finite generating-history prefix π \pi π ending at state x x x together with the conformance evidence recorded for that prefix, and whose output is a subset Δ ( π ) ⊆ C ( x ) \Delta(\pi) \subseteq C(x) Δ ( π ) ⊆ C ( x ) . The rule is fixed across all extensions. In the general model the rule is an exogenous input: the framework does not constrain what Δ \Delta Δ may depend on, and no complexity claim is made for it. The restriction used for the recoverability classification—state-determined and effectively evaluable—is stated in § 7.1 and repeated where it is invoked.
A finite realized history ρ \rho ρ consists of a generating-history prefix π = ( f 1 , … , f n ) \pi= (f_1,\ldots,f_n) π = ( f 1 , … , f n ) , with states x 0 , … , x n x_0,\ldots,x_n x 0 , … , x n , together with the realized subsets assigned by Δ \Delta Δ to its prefixes. We stipulate Δ ( π ∣ 0 ) = C ( x 0 ) \Delta(\pi\mid0) = C(x_0) Δ ( π ∣ 0 ) = C ( x 0 ) at the initial prefix. Write C i r e = Δ ( π ∣ i ) ⊆ C ( x i ) C_i^{\mathrm{re}} = \Delta(\pi\mid i) \subseteq C(x_i) C i re = Δ ( π ∣ i ) ⊆ C ( x i ) . The stipulation C 0 r e = C ( x 0 ) C_0^{\mathrm{re}} = C(x_0) C 0 re = C ( x 0 ) is an initial-realization convention.
Given γ 0 ∈ C ( x 0 ) \gamma_0 \in C(x_0) γ 0 ∈ C ( x 0 ) , the realized lifts are
L 0 r e ( γ 0 ) = { γ 0 } , L i r e ( γ 0 ) = R f i ( L i − 1 r e ( γ 0 ) ) ∩ C i r e . (29) L_0^{\mathrm{re}}(\gamma_0) = \{\gamma_0\}, \qquad L_i^{\mathrm{re}}(\gamma_0) = R_{f_i}\bigl(L_{i-1}^{\mathrm{re}}(\gamma_0)\bigr) \cap C_i^{\mathrm{re}}. \tag*{(29)} L 0 re ( γ 0 ) = { γ 0 } , L i re ( γ 0 ) = R f i ( L i − 1 re ( γ 0 ) ) ∩ C i re . (29)
For a path segment p p p along ρ \rho ρ , we write R p r e ( γ ) R_p^{\mathrm{re}}(\gamma) R p re ( γ ) for the realized lift obtained by the same recursion along that segment, including intersection with the realized subset at each intermediate state. The statuses D e a d r e \mathrm{Dead}^{\mathrm{re}} Dead re , P r e s r e \mathrm{Pres}^{\mathrm{re}} Pres re , D i l r e \mathrm{Dil}^{\mathrm{re}} Dil re are defined from L i r e L_i^{\mathrm{re}} L i re exactly as the stipulated statuses are defined from L i L_i L i .
Realized death is L i r e ( γ 0 ) = ∅ L_i^{\mathrm{re}}(\gamma_0) = \varnothing L i re ( γ 0 ) = ∅ for some stage i i i .
Remark 9 (Realization cannot create stipulated branches). For every γ 0 \gamma_0 γ 0 and every finite realized history ρ \rho ρ , L i r e ( γ 0 ) ⊆ L i ( γ 0 ) ∩ C i r e L_i^{\mathrm{re}}(\gamma_0) \subseteq L_i(\gamma_0) \cap C_i^{\mathrm{re}} L i re ( γ 0 ) ⊆ L i ( γ 0 ) ∩ C i re for all i i i , so ∣ L i r e ( γ 0 ) ∣ ≤ ∣ L i ( γ 0 ) ∣ |L_i^{\mathrm{re}}(\gamma_0)| \le|L_i(\gamma_0)| ∣ L i re ( γ 0 ) ∣ ≤ ∣ L i ( γ 0 ) ∣ : realization cannot create a branch absent from the stipulated structure. If γ 0 \gamma_0 γ 0 is Dead along ρ \rho ρ under the stipulated structure then it is D e a d r e \mathrm{Dead}^{\mathrm{re}} Dead re , and if it is Pres then it is P r e s r e \mathrm{Pres}^{\mathrm{re}} Pres re or D e a d r e \mathrm{Dead}^{\mathrm{re}} Dead re . A diluted lineage may be realized as diluted, preserved, or dead: if all but one of its stipulated branches are unrealized, the realized lift has cardinality one at every stage, so the lineage is P r e s r e \mathrm{Pres}^{\mathrm{re}} Pres re even though it is Dil in the stipulated structure. The inclusion is by induction: L 0 r e = L 0 L_0^{\mathrm{re}} = L_0 L 0 re = L 0 , and if L i − 1 r e ⊆ L i − 1 L_{i-1}^{\mathrm{re}} \subseteq L_{i-1} L i − 1 re ⊆ L i − 1 then monotonicity of R f i R_{f_i} R f i on subsets gives L i r e = R f i ( L i − 1 r e ) ∩ C i r e ⊆ R f i ( L i − 1 ) ∩ C i r e = L i ∩ C i r e L_i^{\mathrm{re}} = R_{f_i}(L_{i-1}^{\mathrm{re}}) \cap C_i^{\mathrm{re}} \subseteq R_{f_i}(L_{i-1}) \cap C_i^{\mathrm{re}} = L_i \cap C_i^{\mathrm{re}} L i re = R f i ( L i − 1 re ) ∩ C i re ⊆ R f i ( L i − 1 ) ∩ C i re = L i ∩ C i re .
Remark 10 (No composition law for realized relations). Composition is a property of the stipulated R R R . The realized lift passes through the realized subset at each intermediate state, so the realized relation along a path can be strictly smaller than the restriction of the composite stipulated relation to realized endpoints. The identification L n = R f n ∘ ⋯ ∘ f 1 L_n = R_{f_n \circ\cdots\circ f_1} L n = R f n ∘ ⋯ ∘ f 1 of Eq. (8) holds for the stipulated structure only.
Realization-cut number
Fix a finite realized history ρ = ( f 1 , … , f n ) \rho= (f_1, \ldots, f_n) ρ = ( f 1 , … , f n ) with n ≥ 1 n \ge1 n ≥ 1 and a continuation γ 0 ∈ C ( x 0 ) \gamma_0 \in C(x_0) γ 0 ∈ C ( x 0 ) that is not stipulated-dead along ρ \rho ρ . Assume the continuation fibers along ρ \rho ρ are finite, so that the path graph defined below is finite. The path graph G ρ ( γ 0 ) G_\rho(\gamma_0) G ρ ( γ 0 ) has as vertices the pairs ( i , ε ) (i,\varepsilon) ( i , ε ) with ε ∈ L i ( γ 0 ) \varepsilon\in L_i(\gamma_0) ε ∈ L i ( γ 0 ) , and an edge ( i − 1 , ε ) → ( i , ε ′ ) (i-1,\varepsilon) \to(i,\varepsilon') ( i − 1 , ε ) → ( i , ε ′ ) whenever ε ′ ∈ R f i ( ε ) \varepsilon' \in R_{f_i}(\varepsilon) ε ′ ∈ R f i ( ε ) . Layer i i i is { i } × L i ( γ 0 ) \{i\} \times L_i(\gamma_0) { i } × L i ( γ 0 ) . Every edge joins consecutive layers, so every path from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) to layer n n n contains exactly one vertex of each layer. A vertex ( i , ε ) (i,\varepsilon) ( i , ε ) is realized if ε ∈ C i r e \varepsilon\in C_i^{\mathrm{re}} ε ∈ C i re . By the recursion in Eq. (29) , an element lies in L i r e ( γ 0 ) L_i^{\mathrm{re}}(\gamma_0) L i re ( γ 0 ) if and only if it is realized and has a predecessor in L i − 1 r e ( γ 0 ) L_{i-1}^{\mathrm{re}}(\gamma_0) L i − 1 re ( γ 0 ) . Hence L i r e ( γ 0 ) L_i^{\mathrm{re}}(\gamma_0) L i re ( γ 0 ) is the set of layer-i i i vertices reachable from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) by a path all of whose vertices are realized.
Let κ n ( γ 0 ) \kappa_n(\gamma_0) κ n ( γ 0 ) be the least cardinality of a set K K K of vertices of G ρ ( γ 0 ) G_\rho(\gamma_0) G ρ ( γ 0 ) , excluding ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) , such that declaring exactly the vertices in K K K unrealized disconnects ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) from layer n n n ; we call it the realization-cut number of γ 0 \gamma_0 γ 0 along ρ \rho ρ . The quantity is defined against a fully realized baseline, and it measures the minimum number of non-realizations required to empty the realized lift. Equivalently, it is a vertex-connectivity measure from the initial continuation to the final layer: larger values mean that more distinct continuation vertices must be made unrealized to block every stipulated path. It measures worst-case combinatorial robustness, not the probability of failure or the behavior of a particular determination process.
The persistence statuses of § 3 classify a lineage as preserved, diluted, or dead. That classification is coarse: two diluted lineages with different branch structures receive the same status. The cut number refines the classification. Among diluted lineages, it measures how many independent realization failures the lineage can survive before the realized lift empties, so it is the robustness counterpart of the branching classification. A preserved lineage has κ n = 1 \kappa_n = 1 κ n = 1 , since a unique path to the terminal layer can be blocked by a single unrealized vertex; a diluted lineage has κ n ≤ min 1 ≤ i ≤ n ∣ L i ( γ 0 ) ∣ \kappa_n \le\min_{1 \le i \le n} |L_i(\gamma_0)| κ n ≤ min 1 ≤ i ≤ n ∣ L i ( γ 0 ) ∣ , so a singleton layer anywhere in layers 1 through n n n caps the cut number at 1 however wide the other layers are. The statuses say whether the lineage branches; the cut number says how much redundancy the branching provides.
Proposition 12 (Realization-cut number). Assume the continuation fibers along ρ \rho ρ are finite, so that G ρ ( γ 0 ) G_\rho(\gamma_0) G ρ ( γ 0 ) is a finite directed graph. With the notation above:
(a) L n r e ( γ 0 ) = ∅ L_n^{\mathrm{re}}(\gamma_0) = \varnothing L n re ( γ 0 ) = ∅ if and only if the set of unrealized vertices of G ρ ( γ 0 ) G_\rho(\gamma_0) G ρ ( γ 0 ) meets every path from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) to layer n n n ; equivalently, γ 0 \gamma_0 γ 0 is D e a d r e \mathrm{Dead}^{\mathrm{re}} Dead re along ρ \rho ρ .
(b) κ n ( γ 0 ) \kappa_n(\gamma_0) κ n ( γ 0 ) equals the maximum number of paths from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) to layer n n n that are pairwise vertex-disjoint except at ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) .
(c) 1 ≤ κ n ( γ 0 ) ≤ min 1 ≤ i ≤ n ∣ L i ( γ 0 ) ∣ 1 \le\kappa_n(\gamma_0) \le\min_{1 \le i \le n} |L_i(\gamma_0)| 1 ≤ κ n ( γ 0 ) ≤ min 1 ≤ i ≤ n ∣ L i ( γ 0 ) ∣ .
(d) κ m ( γ 0 ) ≥ κ n ( γ 0 ) \kappa_m(\gamma_0) \ge\kappa_n(\gamma_0) κ m ( γ 0 ) ≥ κ n ( γ 0 ) for 1 ≤ m ≤ n 1 \le m \le n 1 ≤ m ≤ n : the cut number does not increase as the target layer is extended.
The cut number measures robustness against arbitrary patterns of vertex non-realization in the stipulated path graph. It is a purely combinatorial quantity.
Proof. (a) By the reachability description, L n r e ( γ 0 ) L_n^{\mathrm{re}}(\gamma_0) L n re ( γ 0 ) is empty exactly when no path from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) to layer n n n consists of realized vertices, that is, when every such path contains an unrealized vertex (( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) itself is realized, since C 0 r e = C ( x 0 ) C_0^{\mathrm{re}}=C(x_0) C 0 re = C ( x 0 ) ). If L i r e L_i^{\mathrm{re}} L i re is empty for some i i i then so is L n r e L_n^{\mathrm{re}} L n re , because R ( ∅ ) = ∅ R(\varnothing)=\varnothing R ( ∅ ) = ∅ ; so D e a d r e \mathrm{Dead}^{\mathrm{re}} Dead re is equivalent to L n r e = ∅ L_n^{\mathrm{re}}=\varnothing L n re = ∅ .
(b) Add a vertex T \mathsf{T} T with an edge from every layer-n n n vertex. Since n ≥ 1 n \ge1 n ≥ 1 , ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) and T \mathsf{T} T are not adjacent. A set of vertices other than ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) and T \mathsf{T} T meets every path from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) to layer n n n if and only if its removal separates ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) from T \mathsf{T} T ; such a set may contain layer-n n n vertices. Menger’s theorem in its vertex form [17 , 18 ] states that, in a finite graph, the minimum size of such a separating set equals the maximum number of internally vertex-disjoint paths from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) to T \mathsf{T} T , and these correspond to paths to layer n n n that are disjoint except at ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) .
(c) Since γ 0 \gamma_0 γ 0 is not stipulated-dead, every L i ( γ 0 ) L_i(\gamma_0) L i ( γ 0 ) is nonempty, so a path to layer n n n exists and κ n ≥ 1 \kappa_n \ge1 κ n ≥ 1 . For 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n , every path from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) to layer n n n contains exactly one vertex of layer i i i , so the set { i } × L i ( γ 0 ) \{i\} \times L_i(\gamma_0) { i } × L i ( γ 0 ) meets every such path, and κ n ≤ ∣ L i ( γ 0 ) ∣ \kappa_n \le\lvert L_i(\gamma_0)\rvert κ n ≤ ∣ L i ( γ 0 )∣ .
(d) Take a family of internally vertex-disjoint paths from ( 0 , γ 0 ) (0,\gamma_0) ( 0 , γ 0 ) to layer n n n achieving the maximum size κ n \kappa_n κ n by part (b). Truncate each path at its first vertex in layer m m m . The truncated paths are internally vertex-disjoint, and each truncated path reaches layer m m m . A path to layer m m m cannot always be extended to layer n n n , but a path to layer n n n can always be truncated at layer m m m . Therefore the maximum number of disjoint paths to layer m m m is at least that to layer n n n , so κ m ≥ κ n \kappa_m \ge\kappa_n κ m ≥ κ n by part (b).
Example 2 (Same lift sizes, different cut numbers). Let ρ = ( f 1 , f 2 , f 3 ) \rho=(f_1,f_2,f_3) ρ = ( f 1 , f 2 , f 3 ) pass through x 0 , … , x 3 x_0,\ldots,x_3 x 0 , … , x 3 , with C ( x 0 ) = { γ 0 } C(x_0)=\{\gamma_0\} C ( x 0 ) = { γ 0 } and C ( x i ) = { u i , v i } C(x_i)=\{u_i,v_i\} C ( x i ) = { u i , v i } for i = 1 , 2 , 3 i=1,2,3 i = 1 , 2 , 3 , in two systems H p a r H_{\mathrm{par}} H par and H f u n H_{\mathrm{fun}} H fun that differ only in their relations. In both, R f 1 ( γ 0 ) = { u 1 , v 1 } R_{f_1}(\gamma_0)=\{u_1,v_1\} R f 1 ( γ 0 ) = { u 1 , v 1 } . In the parallel system H p a r H_{\mathrm{par}} H par ,
R f 2 ( u 1 ) = { u 2 } , R f 2 ( v 1 ) = { v 2 } , R f 3 ( u 2 ) = { u 3 } , R f 3 ( v 2 ) = { v 3 } . R_{f_2}(u_1)=\{u_2\},\qquad R_{f_2}(v_1)=\{v_2\},\qquad R_{f_3}(u_2)=\{u_3\},\qquad R_{f_3}(v_2)=\{v_3\}. R f 2 ( u 1 ) = { u 2 } , R f 2 ( v 1 ) = { v 2 } , R f 3 ( u 2 ) = { u 3 } , R f 3 ( v 2 ) = { v 3 } . In the funnel system H f u n H_{\mathrm{fun}} H fun ,
R f 2 ( u 1 ) = { u 2 } , R f 2 ( v 1 ) = { u 2 , v 2 } , R f 3 ( u 2 ) = { u 3 , v 3 } , R f 3 ( v 2 ) = ∅ . R_{f_2}(u_1)=\{u_2\},\qquad R_{f_2}(v_1)=\{u_2,v_2\},\qquad R_{f_3}(u_2)=\{u_3,v_3\},\qquad R_{f_3}(v_2)=\varnothing. R f 2 ( u 1 ) = { u 2 } , R f 2 ( v 1 ) = { u 2 , v 2 } , R f 3 ( u 2 ) = { u 3 , v 3 } , R f 3 ( v 2 ) = ∅ . In both systems ∣ L i ( γ 0 ) ∣ = 1 , 2 , 2 , 2 \lvert L_i(\gamma_0)\rvert=1,2,2,2 ∣ L i ( γ 0 )∣ = 1 , 2 , 2 , 2 for i = 0 , 1 , 2 , 3 i=0,1,2,3 i = 0 , 1 , 2 , 3 , so γ 0 \gamma_0 γ 0 is diluted along ρ \rho ρ with the same cardinality profile and no empty lift. The persistence statuses and the layer sizes do not separate the two. The cut number does. In H p a r H_{\mathrm{par}} H par the chains u 1 u 2 u 3 u_1u_2u_3 u 1 u 2 u 3 and v 1 v 2 v 3 v_1v_2v_3 v 1 v 2 v 3 are vertex-disjoint, so κ 3 ( γ 0 ) = 2 \kappa_3(\gamma_0)=2 κ 3 ( γ 0 ) = 2 . In H f u n H_{\mathrm{fun}} H fun the continuation v 2 v_2 v 2 belongs to the lift but has no successor, so every path to layer 3 3 3 passes through ( 2 , u 2 ) (2,u_2) ( 2 , u 2 ) , and κ 3 ( γ 0 ) = 1 \kappa_3(\gamma_0)=1 κ 3 ( γ 0 ) = 1 .
The difference is operational in the following sense. Suppose the determination process can leave at most one vertex unrealized, in any pattern. In H p a r H_{\mathrm{par}} H par the realized lift of γ 0 \gamma_0 γ 0 is nonempty whichever single vertex fails. In H f u n H_{\mathrm{fun}} H fun the single failure of ( 2 , u 2 ) (2,u_2) ( 2 , u 2 ) empties it, while the failure of ( 2 , v 2 ) (2,v_2) ( 2 , v 2 ) or of either layer-1 1 1 vertex is harmless. A minimum cut also says where the fragility sits: here it is the vertex ( 2 , u 2 ) (2,u_2) ( 2 , u 2 ) , which is where redundancy would have to be added, or where realization would have to be verified most carefully, to raise κ 3 \kappa_3 κ 3 . This is a worst-case statement about a bounded number of failures, in the sense of the following remark, and not a probability, and it concerns reaching the terminal layer, not whether an excluded coordinate can be corrected.
Remark 12 (Operational meaning of the cut number). The cut number measures robustness against arbitrary patterns of vertex non-realization. The conformance-determination process may produce only some of these patterns. A determination-constrained version would require a separate specification of which failure patterns the realization layer permits. The cut number treats vertex non-realizations as combinatorially available failure events and does not model correlations among them; a constrained robustness measure would require an additional specification of which failure sets the realization process permits. The cut number is a structural quantity of the fully realized path graph. Reading it as tolerance to failure requires an additional assumption on the determination process: a bound on how many vertices it can leave unrealized. If at most κ n − 1 \kappa_n-1 κ n − 1 vertices can be unrealized, in any pattern and with any correlation, the lift cannot be emptied; no independence assumption is needed for this worst-case guarantee, and independence matters only for probabilistic statements. Without such a bound, a large cut number does not by itself guarantee that a real determination process fails to empty the lift.
Remark 13 (Computational status of the cut number). Once the path ρ \rho ρ is fixed, the path graph G ρ ( γ 0 ) G_\rho(\gamma_0) G ρ ( γ 0 ) has size polynomial in the extensional input, and κ n ( γ 0 ) \kappa_n(\gamma_0) κ n ( γ 0 ) is computable in polynomial time by max-flow with vertex splitting (equivalently, by the standard algorithmic proof of Menger’s theorem). This contrasts with the unrestricted death-existence problem of Appendix § 12 , which is PSPACE-hard: hardness enters in searching over which path to take, not in evaluating robustness along a fixed path.
Remark 14 (Relation to recoverability). The cut number and the recoverability predicates of § 7 are read off the same lifts, and Menger’s theorem applies to both. Work under the realized definitions of Appendix § 14 , with finite fibers, and let ρ ′ \rho' ρ ′ be a generating history of length n n n together with an admissible recognition continuation.
Lineage death. Let γ 0 ∈ I 0 \gamma_0 \in I_0 γ 0 ∈ I 0 . If fewer than κ n ( γ 0 ) \kappa_n(\gamma_0) κ n ( γ 0 ) vertices of G ρ ′ ( γ 0 ) G_{\rho'}(\gamma_0) G ρ ′ ( γ 0 ) are unrealized, the set of unrealized vertices is not a cut, so L n r e ( γ 0 ) ≠ ∅ L_n^{\mathrm{re}}(\gamma_0) \ne\varnothing L n re ( γ 0 ) = ∅ by Proposition 12(a),(b). Emptiness at an earlier stage persists to stage n n n , so no lineage-death event for γ 0 \gamma_0 γ 0 is generated at any prefix of ρ ′ \rho' ρ ′ . If this holds for every γ 0 ∈ I 0 \gamma_0 \in I_0 γ 0 ∈ I 0 , the requirement of Recover a v a i l \operatorname{Recover}_{\mathrm{avail}} Recover avail that F ( ρ ′ ) F(\rho') F ( ρ ′ ) contain no lineage-death event is met. The condition is sufficient, not necessary.
Corrective routes. Let e = ( p e , γ ) e=(p_e,\gamma) e = ( p e , γ ) be an unresolved exclusion event at state x x x , and let G G G be the path graph of the segment of ρ ′ \rho' ρ ′ from x x x , with root ( 0 , γ ) (0,\gamma) ( 0 , γ ) and vertices ( i , δ ) (i,\delta) ( i , δ ) , δ \delta δ in the stipulated lift of γ \gamma γ after i i i steps. Call ( i , δ ) (i,\delta) ( i , δ ) with i ≥ 1 i\geq1 i ≥ 1 a witness vertex if ( η , δ ) (\eta,\delta) ( η , δ ) is a corrective route witness for e e e on ρ ′ \rho' ρ ′ , where η \eta η is the prefix of ρ ′ \rho' ρ ′ ending at layer i i i . Add a sink ⊤ \top ⊤ with an edge from every witness vertex. The root is not a witness vertex, so it is not adjacent to ⊤ \top ⊤ , and Menger’s theorem gives: the least number of vertices other than the root and ⊤ \top ⊤ whose removal separates the root from ⊤ \top ⊤ equals the maximum number of root–⊤ \top ⊤ paths that are pairwise vertex-disjoint except at the root and ⊤ \top ⊤ . A non-realized vertex is deleted, since it cannot be a witness, so no set of non-realizations smaller than this number removes every witness for e e e on ρ ′ \rho' ρ ′ .
So the cut number measures how robust the existence conditions inside Recover a v a i l \operatorname{Recover}_{\mathrm{avail}} Recover avail are to partial realization; it does not enter the recognition conditions B n ( γ ) ( δ ) = ⋃ δ ′ ∈ S ^ ( γ , δ ) δ ′ = 1 B_n(\gamma)(\delta)=\mathop{\bigcup}\limits_{\delta' \in\widehat{S}(\gamma,\delta)} \delta'=1 B n ( γ ) ( δ ) = δ ′ ∈ S ( γ , δ ) ⋃ δ ′ = 1 . Along a given extension both are computed by maximum flow in polynomial time, so the hardness of Proposition 10 lies in choosing the extension and in requiring one extension to serve every unresolved event.*
Remark 15 (The cut number is path-indexed). The cut number κ n ( γ 0 ) \kappa_n(\gamma_0) κ n ( γ 0 ) is defined relative to a fixed realized history ρ \rho ρ . Two different histories reaching the same state may traverse different modifications and carry different stipulated lifts, and the cut numbers along them are separate quantities. The framework does not define an aggregate robustness measure over a set of paths. A natural definition would take the minimum of κ n \kappa_n κ n over an admissible set of histories, or the minimum over histories that respect the determination process, but the choice of admissible set is a governance act of the same kind as the choice of D D D . Aggregation across paths, and the choice of an aggregate, are not treated here.
The cut number concerns reaching the terminal layer. Whether a particular excluded coordinate can be corrected also depends on which terminal vertices descend from it, lie in D D D , and are admitted by S S S , so a lineage with a large κ n \kappa_n κ n may still have no corrective route.
A preserved lineage has ∣ L i ∣ = 1 |L_i| = 1 ∣ L i ∣ = 1 at every stage, hence κ n = 1 \kappa_n = 1 κ n = 1 by (c): a single unrealized link kills it. A diluted lineage has κ n ≤ min i ∣ L i ∣ \kappa_n \le\min_i |L_i| κ n ≤ min i ∣ L i ∣ , so a singleton layer anywhere in layers 1 1 1 through n n n caps κ n \kappa_n κ n at 1 1 1 , however wide the other layers are. The statuses classify structural branching, whereas κ n \kappa_n κ n counts how many independent realization failures can be tolerated; the two are different quantities. Conversely, κ n ≥ 2 \kappa_n \ge2 κ n ≥ 2 requires that γ 0 \gamma_0 γ 0 be diluted along the prefix: a preserved lineage has a unique path to the terminal layer and cannot have more than one independent path.
In the abstract model, the stipulated lift of γ 0 \gamma_0 γ 0 along P A P_A P A has cardinalities 1 , 1 , 1 , 2 , 2 , 2 1,1,1,2,2,2 1 , 1 , 1 , 2 , 2 , 2 at x 0 , x 1 , x 2 , x 4 , x 5 , x 6 x_0,x_1,x_2,x_4,x_5,x_6 x 0 , x 1 , x 2 , x 4 , x 5 , x 6 . By (c), κ 5 ( γ 0 ) ≤ ∣ L 1 ( γ 0 ) ∣ = 1 \kappa_5(\gamma_0) \le|L_1(\gamma_0)| = 1 κ 5 ( γ 0 ) ≤ ∣ L 1 ( γ 0 ) ∣ = 1 , so γ 0 \gamma_0 γ 0 is diluted but exactly as fragile as a preserved lineage: leaving γ 1 \gamma_1 γ 1 or γ 2 \gamma_2 γ 2 unrealized kills it. For the lineage of γ 2 \gamma_2 γ 2 alone along ( d , f , g ) (d,f,g) ( d , f , g ) , the S S S -chain γ 4 S , γ 5 S , γ 6 S \gamma_4^S,\gamma_5^S,\gamma_6^S γ 4 S , γ 5 S , γ 6 S and the W W W -chain γ 4 W , γ 5 W , γ 6 W \gamma_4^W,\gamma_5^W,\gamma_6^W γ 4 W , γ 5 W , γ 6 W are vertex-disjoint paths, so κ = 2 \kappa= 2 κ = 2 . Survival is not the same as every layer being nonempty: realizing γ 4 S \gamma_4^S γ 4 S and γ 5 W \gamma_5^W γ 5 W but nothing else on the fork empties the lineage, because there is no edge between the chains.
Determinations
A conformance determination is recorded as
det i = ( x i , ρ ∣ i , C i r e , ev i , dec i ) , \operatorname{det}_i = (x_i,\rho|_i,C_i^{\mathrm{re}},\operatorname{ev}_i,\operatorname{dec}_i), det i = ( x i , ρ ∣ i , C i re , ev i , dec i ) ,
where ev i \operatorname{ev}_i ev i is the evidence on which it rests and dec i \operatorname{dec}_i dec i identifies the decider. The particular schema is illustrative; what matters is that the determination record separates realization from stipulation and recognition, and that it carries the evidence and the decider so that the judgment is attributable. A determination assigns each continuation in C ( x i ) C(x_i) C ( x i ) to the realized subset C i r e C_i^{\mathrm{re}} C i re or its complement. The assignment may incorporate evidential uncertainty; the framework records the determination rather than prescribing how uncertainty is resolved. Whether the determination was correct is outside the formalism.
Whether a symmetry-breaking determination reflects system-side evidence or normative supplementation is a classification of its recorded justification, not a property visible to the augmented structure ( H , C , R , C ρ r e ) (H,C,R,C_\rho^{\mathrm{re}}) ( H , C , R , C ρ re ) .
Underdetermination with determinations
Effect on recoverability
The main text uses the full-realization baseline D ρ r e = D D^{\mathrm{re}}_{\rho}=D D ρ re = D . Under partial realization, the same definitions use realized lifts and domains. At stage i i i of a realized history ρ \rho ρ , with reached state x i x_i x i , the realized decision domain is D ρ i r e ( x i ) = D ( x i ) ∩ C i r e D^{\mathrm{re}}_{\rho_i}(x_i)=D(x_i)\cap C^{\mathrm{re}}_i D ρ i re ( x i ) = D ( x i ) ∩ C i re and the recognition state is B ρ i ( x i ) B_{\rho_i}(x_i) B ρ i ( x i ) . An exclusion event is a pair ( ρ e , γ ) (\rho_e,\gamma) ( ρ e , γ ) with
γ ∈ D ρ e r e ( x ) , B ρ e ( x ) ( γ ) = E , \gamma\in D^{\mathrm{re}}_{\rho_e}(x),\qquad B_{\rho_e}(x)(\gamma)=\mathrm{E}, γ ∈ D ρ e re ( x ) , B ρ e ( x ) ( γ ) = E ,
where ρ e \rho_e ρ e is a finite realized history ending at x x x and the recognition state is B ρ e B_{\rho_e} B ρ e . A lineage-death event is a pair ( ρ e , γ 0 ) (\rho_e,\gamma_0) ( ρ e , γ 0 ) with γ 0 ∈ I 0 \gamma_0\in I_0 γ 0 ∈ I 0 , where ρ e \rho_e ρ e ends at the first stage at which the realized lift L i r e ( γ 0 ) L^{\mathrm{re}}_i(\gamma_0) L i re ( γ 0 ) is empty. For a path segment p p p along a realized history, write R p r e ( γ ) R^{\mathrm{re}}_p(\gamma) R p re ( γ ) for the corresponding recursively realized lift, with the realized subset intersected at each intermediate stage. A corrective inscription for an exclusion event at a later state y y y , reached at stage j j j along an extension, may inscribe a descendant δ \delta δ satisfying
δ ∈ R p r e ( γ ) ∩ D ρ j r e ( y ) , B ρ j ( y ) ( δ ) = U , S ( y , δ ) = inscribed , \delta\in R^{\mathrm{re}}_p(\gamma)\cap D^{\mathrm{re}}_{\rho_j}(y),\qquad B_{\rho_j}(y)(\delta)=\mathrm{U},\qquad S(y,\delta)=\text{inscribed}, δ ∈ R p re ( γ ) ∩ D ρ j re ( y ) , B ρ j ( y ) ( δ ) = U , S ( y , δ ) = inscribed ,
followed by the admissible transition
B ρ j + 1 ( y ) ( δ ) = I . B_{\rho_{j+1}}(y)(\delta)=\mathrm{I}. B ρ j + 1 ( y ) ( δ ) = I .
Thus realization supplies eligibility, S S S supplies recognition admissibility, and the recognition history records occurrence. The criterion S S S is defined on all of C C C , but in the realized setting its value at a coordinate outside D ρ j r e ( y ) D^{\mathrm{re}}_{\rho_j}(y) D ρ j re ( y ) is not consulted: the realized decision domain is D ρ j r e ( y ) = D ( y ) ∩ C j r e D^{\mathrm{re}}_{\rho_j}(y)=D(y)\cap C^{\mathrm{re}}_j D ρ j re ( y ) = D ( y ) ∩ C j re , and a coordinate excluded from it by non-realization receives no decision. A realized lineage-death event is attached to the realized history on which it is generated, and admits no corrective inscription along extensions of that history: on any extension of ρ e \rho_e ρ e , the realized lift stays empty by the recursion
L i + 1 r e = R f i + 1 ( L i r e ) ∩ C i + 1 r e , L^{\mathrm{re}}_{i+1}=R_{f_{i+1}}(L^{\mathrm{re}}_i)\cap C^{\mathrm{re}}_{i+1}, L i + 1 re = R f i + 1 ( L i re ) ∩ C i + 1 re ,
under which R f i + 1 ( ∅ ) = ∅ R_{f_{i+1}}(\varnothing)=\varnothing R f i + 1 ( ∅ ) = ∅ , not by a composition law for the realized relation. The qualification is local to ρ e \rho_e ρ e : a different history with a different determination may have a nonempty realized lift for the same stipulated lineage.
The determination process remains fixed across quantified extensions; later outcomes may still affect whether a required descendant is realized. The determination record identifies the decider responsible for those outcomes.
Detailed Calculations for the Abstract Model
For the A branch,
R d ( R b ( γ 1 ) ) = R d ( { γ 2 } ) = { γ 4 S , γ 4 W } . (30) R_d(R_b(\gamma_1))=R_d(\{\gamma_2\})=\{\gamma_4^{S},\gamma_4^{W}\}. \tag*{(30)} R d ( R b ( γ 1 )) = R d ({ γ 2 }) = { γ 4 S , γ 4 W } . (30)
For the B branch, the stipulated lift of γ 0 \gamma_0 γ 0 becomes empty at c c c , so
R c ( R a ( γ 0 ) ) = ∅ . (31) R_c(R_a(\gamma_0))=\varnothing. \tag*{(31)} R c ( R a ( γ 0 )) = ∅ . (31)
C ( x 4 ) C(x_4) C ( x 4 ) is the continuation space available at x 4 x_4 x 4 ; the reachable subset along P A P_A P A is { α 4 , β 4 , γ 4 S , γ 4 W } \{\alpha_4,\beta_4,\gamma_4^{S},\gamma_4^{W}\} { α 4 , β 4 , γ 4 S , γ 4 W } , and along P B P_B P B is { α 4 , β 4 } \{\alpha_4,\beta_4\} { α 4 , β 4 } .
For α \alpha α and β \beta β , every local lift has cardinality one, so
status P A ( α 0 ) = status P B ( α 0 ) = P r e s , status P A ( β 0 ) = status P B ( β 0 ) = P r e s . \operatorname{status}_{P_A}(\alpha_0)=\operatorname{status}_{P_B}(\alpha_0)=\mathrm{Pres},\qquad
\operatorname{status}_{P_A}(\beta_0)=\operatorname{status}_{P_B}(\beta_0)=\mathrm{Pres}. status P A ( α 0 ) = status P B ( α 0 ) = Pres , status P A ( β 0 ) = status P B ( β 0 ) = Pres .
For γ \gamma γ , ∣ R d ( R b ( γ 1 ) ) ∣ = 2 |R_d(R_b(\gamma_1))|=2 ∣ R d ( R b ( γ 1 )) ∣ = 2 , so status P A ( γ 0 ) = D i l \operatorname{status}_{P_A}(\gamma_0)=\mathrm{Dil} status P A ( γ 0 ) = Dil , whereas R c ( R a ( γ 0 ) ) = ∅ R_c(R_a(\gamma_0))=\varnothing R c ( R a ( γ 0 )) = ∅ and therefore status P B ( γ 0 ) = D e a d \operatorname{status}_{P_B}(\gamma_0)=\mathrm{Dead} status P B ( γ 0 ) = Dead , both under the stipulated structure.
The nonempty generating relations used in the example are
R a ( α 0 ) = { α 1 } , R a ( β 0 ) = { β 1 } , R a ( γ 0 ) = { γ 1 } , R b ( α 1 ) = { α 2 } , R b ( β 1 ) = { β 2 } , R b ( γ 1 ) = { γ 2 } , R c ( α 1 ) = { α 3 } , R c ( β 1 ) = { β 3 } , R c ( γ 1 ) = ∅ , R d ( α 2 ) = { α 4 } , R d ( β 2 ) = { β 4 } , R d ( γ 2 ) = { γ 4 S , γ 4 W } , R e ( α 3 ) = { α 4 } , R e ( β 3 ) = { β 4 } , R e ( γ 3 ) = ∅ , R f ( α 4 ) = { α 5 } , R f ( β 4 ) = { β 5 } , R f ( γ 4 S ) = { γ 5 S } , R f ( γ 4 W ) = { γ 5 W } , R g ( α 5 ) = { α 6 } , R g ( β 5 ) = { β 6 } , R g ( γ 5 S ) = { γ 6 S } , R g ( γ 5 W ) = { γ 6 W } . \begin{aligned}
R_a(\alpha_0) &= \{\alpha_1\}, & R_a(\beta_0) &= \{\beta_1\}, & R_a(\gamma_0) &= \{\gamma_1\}, \\
R_b(\alpha_1) &= \{\alpha_2\}, & R_b(\beta_1) &= \{\beta_2\}, & R_b(\gamma_1) &= \{\gamma_2\}, \\
R_c(\alpha_1) &= \{\alpha_3\}, & R_c(\beta_1) &= \{\beta_3\}, & R_c(\gamma_1) &= \varnothing, \\
R_d(\alpha_2) &= \{\alpha_4\}, & R_d(\beta_2) &= \{\beta_4\}, & R_d(\gamma_2) &= \{\gamma_4^S,\gamma_4^W\}, \\
R_e(\alpha_3) &= \{\alpha_4\}, & R_e(\beta_3) &= \{\beta_4\}, & R_e(\gamma_3) &= \varnothing, \\
R_f(\alpha_4) &= \{\alpha_5\}, & R_f(\beta_4) &= \{\beta_5\}, & R_f(\gamma_4^S) &= \{\gamma_5^S\}, & R_f(\gamma_4^W) &= \{\gamma_5^W\}, \\
R_g(\alpha_5) &= \{\alpha_6\}, & R_g(\beta_5) &= \{\beta_6\}, & R_g(\gamma_5^S) &= \{\gamma_6^S\}, & R_g(\gamma_5^W) &= \{\gamma_6^W\}.
\end{aligned} R a ( α 0 ) R b ( α 1 ) R c ( α 1 ) R d ( α 2 ) R e ( α 3 ) R f ( α 4 ) R g ( α 5 ) = { α 1 } , = { α 2 } , = { α 3 } , = { α 4 } , = { α 4 } , = { α 5 } , = { α 6 } , R a ( β 0 ) R b ( β 1 ) R c ( β 1 ) R d ( β 2 ) R e ( β 3 ) R f ( β 4 ) R g ( β 5 ) = { β 1 } , = { β 2 } , = { β 3 } , = { β 4 } , = { β 4 } , = { β 5 } , = { β 6 } , R a ( γ 0 ) R b ( γ 1 ) R c ( γ 1 ) R d ( γ 2 ) R e ( γ 3 ) R f ( γ 4 S ) R g ( γ 5 S ) = { γ 1 } , = { γ 2 } , = ∅ , = { γ 4 S , γ 4 W } , = ∅ , = { γ 5 S } , = { γ 6 S } , R f ( γ 4 W ) R g ( γ 5 W ) = { γ 5 W } , = { γ 6 W } .
The displayed relations, including the explicitly empty relations, exhaust the generating compatibility relations for the core system. The displayed relations for α \alpha α and β \beta β through f f f and g g g are stipulated as singleton continuation relations; relations for composite modifications then follow from the composition condition.
For the local decision domain concentrated at x 4 x_4 x 4 , let D ( x 0 ) = I 0 D(x_0)=I_0 D ( x 0 ) = I 0 , let D ( x 4 ) = { γ 4 S , γ 4 W } D(x_4)=\{\gamma_4^S,\gamma_4^W\} D ( x 4 ) = { γ 4 S , γ 4 W } , and let D ( x ) = ∅ D(x)=\varnothing D ( x ) = ∅ elsewhere in the core system. Along P A P_A P A the realized decision domain at x 4 x_4 x 4 is D P A r e ( x 4 ) = { γ 4 S , γ 4 W } D^{\mathrm{re}}_{P_A}(x_4)=\{\gamma_4^S,\gamma_4^W\} D P A re ( x 4 ) = { γ 4 S , γ 4 W } . Along P B P_B P B , a conformance determination is stipulated that excludes both γ 4 S \gamma_4^S γ 4 S and γ 4 W \gamma_4^W γ 4 W from C P B r e ( x 4 ) C^{\mathrm{re}}_{P_B}(x_4) C P B re ( x 4 ) , so D P B r e ( x 4 ) = ∅ D^{\mathrm{re}}_{P_B}(x_4)=\varnothing D P B re ( x 4 ) = ∅ by determination. Writing only the noninitial x 4 x_4 x 4 component of the possible assignment, the four possibilities are in bijection with the four elements of 2 D ( x 4 ) 2^{D(x_4)} 2 D ( x 4 ) .
For recoverability, suppose a finite prefix ρ 10 \rho_{10} ρ 10 contains exactly one unresolved exclusion event ( ρ 10 , γ 10 ) (\rho_{10},\gamma_{10}) ( ρ 10 , γ 10 ) at state x 10 x_{10} x 10 and no lineage-death events. A subsequent modification r : x 10 → x 13 r:x_{10}\to x_{13} r : x 10 → x 13 with R r ( γ 10 ) = { γ 13 S } R_r(\gamma_{10})=\{\gamma_{13}^S\} R r ( γ 10 ) = { γ 13 S } , where γ 13 S \gamma_{13}^S γ 13 S is a decision coordinate not yet adjudicated, then provides a corrective route for the unique unresolved exclusion event. Since there are no lineage-death events and no other unresolved exclusions, the existence of this route establishes Recover a v a i l ( ρ 10 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_{10}) Recover avail ( ρ 10 ) for this example. The prefix ρ 10 \rho_{10} ρ 10 alone does not establish this.
If instead L i ( γ 0 ) = ∅ L_i(\gamma_0)=\varnothing L i ( γ 0 ) = ∅ at some stage i i i of ρ 10 \rho_{10} ρ 10 under the stipulated structure, the resulting lineage-death event would remain unresolved on every extension of that prefix, and Recover a v a i l ( ρ 10 ) \operatorname{Recover}_{\mathrm{avail}}(\rho_{10}) Recover avail ( ρ 10 ) would fail regardless of any corrective route for the exclusion event.
The automorphism group of the core system
Let σ ∈ Aut ∗ \sigma\in\operatorname{Aut}_* σ ∈ Aut ∗ be a symmetry of the pointed structure ( H , C , R , x 0 , I 0 , D ) (H,C,R,x_0,I_0,D) ( H , C , R , x 0 , I 0 , D ) of § 6 . We verify that Aut ∗ = Z / 2 × Z / 2 \operatorname{Aut}_*=\mathbb{Z}/2\times\mathbb{Z}/2 Aut ∗ = Z /2 × Z /2 .
States are fixed. By definition σ ( x 0 ) = x 0 \sigma(x_0)=x_0 σ ( x 0 ) = x 0 . The only modification out of x 0 x_0 x 0 is a a a , so σ ( a ) = a \sigma(a)=a σ ( a ) = a , hence σ ( x 1 ) = x 1 \sigma(x_1)=x_1 σ ( x 1 ) = x 1 . From x 1 x_1 x 1 the modifications b : x 1 → x 2 b:x_1\to x_2 b : x 1 → x 2 and c : x 1 → x 3 c:x_1\to x_3 c : x 1 → x 3 are the only ones, so σ \sigma σ permutes { b , c } \{b,c\} { b , c } , hence { x 2 , x 3 } \{x_2,x_3\} { x 2 , x 3 } . Were σ \sigma σ to swap b b b and c c c , we would have σ ( x 2 ) = x 3 \sigma(x_2)=x_3 σ ( x 2 ) = x 3 and σ ( x 3 ) = x 2 \sigma(x_3)=x_2 σ ( x 3 ) = x 2 , and so σ \sigma σ would map the fiber C ( x 2 ) C(x_2) C ( x 2 ) onto C ( x 3 ) C(x_3) C ( x 3 ) . Then σ ( R d ( γ 2 ) ) = R e ( σ ( γ 2 ) ) \sigma(R_d(\gamma_2))=R_e(\sigma(\gamma_2)) σ ( R d ( γ 2 )) = R e ( σ ( γ 2 )) is required, but ∣ R d ( γ 2 ) ∣ = 2 |R_d(\gamma_2)|=2 ∣ R d ( γ 2 ) ∣ = 2 while every relation out of C ( x 3 ) C(x_3) C ( x 3 ) has size at most 1 1 1 (R e ( α 3 ) = { α 4 } R_e(\alpha_3)=\{\alpha_4\} R e ( α 3 ) = { α 4 } , R e ( β 3 ) = { β 4 } R_e(\beta_3)=\{\beta_4\} R e ( β 3 ) = { β 4 } , R e ( γ 3 ) = ∅ R_e(\gamma_3)=\varnothing R e ( γ 3 ) = ∅ ). Contradiction. So σ \sigma σ fixes b , c , x 2 , x 3 b,c,x_2,x_3 b , c , x 2 , x 3 individually, and then fixes d , e , x 4 d,e,x_4 d , e , x 4 , and, by the same argument on f , g f,g f , g , the states x 5 , x 6 x_5,x_6 x 5 , x 6 .
The γ \gamma γ -chain up to x 3 x_3 x 3 is fixed. Suppose σ ( γ 0 ) = α 0 \sigma(\gamma_0)=\alpha_0 σ ( γ 0 ) = α 0 . Then equivariance of R a R_a R a gives σ ( γ 1 ) = α 1 \sigma(\gamma_1)=\alpha_1 σ ( γ 1 ) = α 1 , of R b R_b R b gives σ ( γ 2 ) = α 2 \sigma(\gamma_2)=\alpha_2 σ ( γ 2 ) = α 2 , and of R d R_d R d gives σ ( R d ( γ 2 ) ) = R d ( α 2 ) \sigma(R_d(\gamma_2))=R_d(\alpha_2) σ ( R d ( γ 2 )) = R d ( α 2 ) . But ∣ R d ( γ 2 ) ∣ = 2 |R_d(\gamma_2)|=2 ∣ R d ( γ 2 ) ∣ = 2 while ∣ R d ( α 2 ) ∣ = 1 |R_d(\alpha_2)|=1 ∣ R d ( α 2 ) ∣ = 1 , and σ \sigma σ is a bijection, so no such σ \sigma σ exists. The same argument excludes σ ( γ 0 ) = β 0 \sigma(\gamma_0)=\beta_0 σ ( γ 0 ) = β 0 . Hence σ \sigma σ fixes γ 0 \gamma_0 γ 0 , and then fixes γ 1 , γ 2 \gamma_1,\gamma_2 γ 1 , γ 2 by the same equivariance. It also fixes γ 3 \gamma_3 γ 3 : equivariance gives R e ( σ ( γ 3 ) ) = σ ( R e ( γ 3 ) ) = ∅ R_e(\sigma(\gamma_3))=\sigma(R_e(\gamma_3))=\varnothing R e ( σ ( γ 3 )) = σ ( R e ( γ 3 )) = ∅ , while R e ( α 3 ) R_e(\alpha_3) R e ( α 3 ) and R e ( β 3 ) R_e(\beta_3) R e ( β 3 ) are nonempty. The γ \gamma γ -fork at x 4 x_{4} x 4 is fixed setwise. The constraint σ ( D ( x 4 ) ) = D ( x 4 ) \sigma(D(x_{4})) = D(x_{4}) σ ( D ( x 4 )) = D ( x 4 ) with D ( x 4 ) = { γ 4 S , γ 4 W } D(x_{4}) = \{\gamma^{S}_{4}, \gamma^{W}_{4}\} D ( x 4 ) = { γ 4 S , γ 4 W } forces σ ( { γ 4 S , γ 4 W } ) = { γ 4 S , γ 4 W } \sigma(\{\gamma^{S}_{4}, \gamma^{W}_{4}\}) = \{\gamma^{S}_{4}, \gamma^{W}_{4}\} σ ({ γ 4 S , γ 4 W }) = { γ 4 S , γ 4 W } . Combined with R f R_{f} R f and R g R_{g} R g (both singletons), this gives the same for { γ 5 S , γ 5 W } \{\gamma^{S}_{5}, \gamma^{W}_{5}\} { γ 5 S , γ 5 W } and { γ 6 S , γ 6 W } \{\gamma^{S}_{6}, \gamma^{W}_{6}\} { γ 6 S , γ 6 W } , and equivariance of R f R_{f} R f and R g R_{g} R g ties the exchange at x 5 x_{5} x 5 and x 6 x_{6} x 6 to the exchange at x 4 x_{4} x 4 : σ \sigma σ swaps all three pairs or none.
The α / β \alpha/\beta α / β layer is fixed or swapped. Since σ \sigma σ fixes γ 0 \gamma_{0} γ 0 and permutes { α 0 , β 0 } \{\alpha_{0}, \beta_{0}\} { α 0 , β 0 } , and the relations R a , R b , R c , R d , R e , R f , R g R_{a}, R_{b}, R_{c}, R_{d}, R_{e}, R_{f}, R_{g} R a , R b , R c , R d , R e , R f , R g act consistently (α ↔ β \alpha\leftrightarrow\beta α ↔ β throughout), either σ \sigma σ fixes α i , β i \alpha_{i}, \beta_{i} α i , β i for all i i i or it swaps them for all i i i .
Generators. Let σ α β \sigma_{\alpha\beta} σ α β swap α i ↔ β i \alpha_{i} \leftrightarrow\beta_{i} α i ↔ β i for all i i i and fix all γ \gamma γ -coordinates. Let σ γ \sigma_{\gamma} σ γ swap γ 4 S ↔ γ 4 W \gamma^{S}_{4} \leftrightarrow\gamma^{W}_{4} γ 4 S ↔ γ 4 W , γ 5 S ↔ γ 5 W \gamma^{S}_{5} \leftrightarrow\gamma^{W}_{5} γ 5 S ↔ γ 5 W , γ 6 S ↔ γ 6 W \gamma^{S}_{6} \leftrightarrow\gamma^{W}_{6} γ 6 S ↔ γ 6 W and fix all α \alpha α - and β \beta β -coordinates. Both are automorphisms of the pointed structure: each preserves x 0 x_{0} x 0 , I 0 I_{0} I 0 (as a set), and D ( x 4 ) D(x_{4}) D ( x 4 ) (as a set), and each commutes with the relations. They commute with each other, and the paragraph above shows that every element of Aut ∗ \operatorname{Aut}_{*} Aut ∗ is one of { i d , σ α β , σ γ , σ α β σ γ } \{\mathrm{id}, \sigma_{\alpha\beta}, \sigma_{\gamma}, \sigma_{\alpha\beta}\sigma_{\gamma}\} { id , σ α β , σ γ , σ α β σ γ } .
Hence Aut ∗ = Z / 2 × Z / 2 \operatorname{Aut}_{*} = \mathbb{Z}/2 \times\mathbb{Z}/2 Aut ∗ = Z /2 × Z /2 , of order four. Its orbits on the coordinates of D D D with x ≠ x 0 x \ne x_{0} x = x 0 are { γ 4 S , γ 4 W } \{\gamma^{S}_{4}, \gamma^{W}_{4}\} { γ 4 S , γ 4 W } , { γ 5 S , γ 5 W } \{\gamma^{S}_{5}, \gamma^{W}_{5}\} { γ 5 S , γ 5 W } , { γ 6 S , γ 6 W } \{\gamma^{S}_{6}, \gamma^{W}_{6}\} { γ 6 S , γ 6 W } , together with the singleton orbits of the α \alpha α - and β \beta β -coordinates that lie in D D D (none, in the core system). The characterization of § 5 then applies directly: the only target set in D D D at a state y ≠ x 0 y \ne x_{0} y = x 0 is { γ 4 S , γ 4 W } \{\gamma^{S}_{4}, \gamma^{W}_{4}\} { γ 4 S , γ 4 W } at x 4 x_{4} x 4 , its orbit meets it in two elements, and so no structural exclusive criterion exists.
Notation
Symbols used throughout the paper are collected below, grouped by topic; the last column gives the section in which each is introduced. Symbols that occur only inside a single proof or construction (for example, the clause continuations ξ ( i ) \xi^{(i)} ξ ( i ) , the variables ν i \nu_{i} ν i and the NFA transition function μ \mu μ in Appendices A and B) are defined where they are used and are not listed.
Table 3.
Table 2 (PDF p. 44).
Table 3.