Introduction
Register and nominal automata. Register automata , introduced by Kaminski and Francez as finite-memory automata [17 ] , are a natural model for systems that process data from infinite alphabets, such as data-manipulating programs and communication protocols. They operate by storing data values in finitely many registers and testing inputs against the stored values for equality. Algorithmically, deterministic register automata are well behaved: language equivalence [28 , 29 ] and minimization [4 ] are efficiently computable.
As a running example, Figure 1 shows a register automaton for the resource language Res(2): at most two resources may be open simultaneously, and a word is accepted once every opened resource has been closed. It uses three states q 0 q_0 q 0 , q 1 q_1 q 1 , q 2 q_2 q 2 and two registers x 1 x_1 x 1 , x 2 x_2 x 2 . An Open(a a a ) transition stores a new resource name a a a in a vacant register, while a Close(a a a )
Figure 1. The resource language Res(2) as a register automaton. The transition function is partial: if a transition is undefined, the automaton rejects the input.
transition releases the resource matching a stored value. Since either open resource may be closed first, q 2 q_2 q 2 needs two Close transitions, one of which reassigns the registers (x 1 : = x 2 x_1 := x_2 x 1 := x 2 ).
Nominal automata [9 ] offer an alternative formulation based on nominal sets [34 ] : sets equipped with an action of permutations of the data values, where each element has finite support. States form an orbit-finite nominal set and transitions are equivariant maps. The permitted permutations are a parameter called the data symmetry [9 ] : the equality symmetry allows every permutation (data compared only for equality, as in Figure 1 ), while the total-order symmetry allows only order-preserving permutations (ordered data). Over the equality symmetry, nominal automata are expressively equivalent to register automata [9 Thm. 6.6] .
The algorithmic gap and local symmetries. Despite their theoretical equivalence, an algorithmic gap separates the two models in practice. For deterministic register automata, Murawski et al. [28 , 29 ] achieved a polynomial-time equivalence check using generating systems , data structures that handle equivalence classes of configurations orbit-wise . In contrast, general-purpose nominal-computation tools, such as Nλ [18 ] and Lois [19 ] , rely on SMT solvers, hiding the orbit structure and leading to a performance bottleneck: “direct custom-made register-automata algorithms are typically faster” [3 ] . Over the total-order symmetry, Ons [40 ] already provides orbit-wise representations via constraint-free arrays. The total-order symmetry can express every language over the equality symmetry, but each equality-symmetry orbit of dimension d d d then splits into up to d ! d! d ! orbits, as detailed in Remark 2.2, so using the data symmetry that matches the language is crucial for efficiency [40 ] .
We identify what blocks the Ons recipe over the equality symmetry: non-trivial local symmetries . In Res(2), the Myhill–Nerode classes with two open resources form the orbit of unordered pairs { a , b } \{a,b\} { a , b } ; each such element is fixed by the non-trivial swap ( a b ) (a\ b) ( a b ) , i.e., carries a non-trivial local symmetry, so the orbit cannot be represented as a set of tuples of distinct atoms (the very format of a constraint-free array). The register automaton of Figure 1 , by contrast, avoids the symmetry by ordering its registers and reassigning them (x 1 : = x 2 x_1 := x_2 x 1 := x 2 ).
Strong nominal sets and the array representation. Our approach builds on strong nominal sets [31 , 37 ] , i.e., nominal sets with trivial local symmetries, as characterized in Proposition 3.3. They coincide with the finitely named sets underlying early history-dependent automata [25 ] , a model that was soon enriched with permutation groups to enable canonical minimization [14 ] . This paper moves in the opposite direction : strong nominal sets correspond exactly to the configuration spaces of register automata, and the very absence of local symmetries is what makes them computationally lightweight. Driven by this observation, our first contribution consolidates known and new categorical equivalences of strong nominal sets into a single chain, shown in Theorem 3.4 , which grounds the rest of the paper:
S N o m ≃ Kl ( T ) ≃ Fam ( I o p ) ≃ Proj ( [ I , S e t ] ) ≃ N S e t f n \mathbf{SNom} \simeq\operatorname{Kl}(T) \simeq\operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) \simeq\operatorname{Proj}([\mathbb{I}, \mathbf{Set}]) \simeq\mathbf{NSet}_{\mathrm{fn}} SNom ≃ Kl ( T ) ≃ Fam ( I op ) ≃ Proj ([ I , Set ]) ≃ NSet fn
where S N o m \mathbf{SNom} SNom denotes the category of strong nominal sets and equivariant maps, I \mathbb{I} I is the category of finite subsets of N \mathbb{N} N and injections, T T T is the monad induced by the adjunction between the category N o m \mathbf{Nom} Nom of nominal sets and the functor category [ [ I ] , S e t ] [\![\mathbb{I}], \mathbf{Set}] [ [ I ] , Set ] [20 , 33 ] , Fam ( I o p ) \operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) Fam ( I op ) is the free coproduct completion of I o p \mathbb{I}^{\mathrm{op}} I op , Proj ( [ I , S e t ] ) \operatorname{Proj}([\mathbb{I}, \mathbf{Set}]) Proj ([ I , Set ]) is the category of projective objects of [ I , S e t ] [\mathbb{I}, \mathbf{Set}] [ I , Set ] , and N S e t f n \mathbf{NSet}_{\mathrm{fn}} NSet fn is the category of finitely named sets [25 ] .
Crucially, the equivalence S N o m ≃ Fam ( I o p ) \mathbf{SNom} \simeq\operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) SNom ≃ Fam ( I op ) yields the concrete, constraint-free array representation developed in § 3.2 . In this representation, each orbit is determined solely by its dimension d d d , an element is a d d d -tuple of distinct atoms, and an equivariant map is an injective array of indices. This representation allows orbits and equivariant maps to be manipulated directly, without relying on SMT solvers.
Projective covers for quotient approximation. A challenge is that strong nominal sets are not closed under quotients. For instance, as Example 4.1 shows, taking the quotient of { ( a , b ) ∣ a ≠ b } \{(a,b)\mid a\ne b\} {( a , b ) ∣ a = b } by ( a , b ) ∼ ( b , a ) (a,b)\sim(b,a) ( a , b ) ∼ ( b , a ) yields { { a , b } ∣ a ≠ b } \{\{a,b\}\mid a\ne b\} {{ a , b } ∣ a = b } , thereby introducing local symmetries. Consequently, the state space of a minimal nominal automaton generally falls outside S N o m \mathrm{SNom} SNom .
Beyond the equivalence S N o m ≃ Proj ( [ I , S e t ] ) \mathrm{SNom}\simeq\operatorname{Proj}([\mathbb{I},\mathbf{Set}]) SNom ≃ Proj ([ I , Set ]) , we show in Theorem 4.2 that every nominal set X X X admits a strong approximation X ′ X' X ′ , obtained from a projective cover in [ I , S e t ] [\mathbb{I},\mathbf{Set}] [ I , Set ] : the induced equivariant surjection p : X ′ ↠ X p:X'\twoheadrightarrow X p : X ′ ↠ X strips away local symmetries yet, by Theorem 4.3, merges no orbits and inflates no dimensions. Since transitions lift along p p p by projectivity, any nominal automaton over a strong alphabet admits a language-equivalent strong lift with the same orbit count and dimensions by Theorem 4.4. Unlike the constructions assembled from known results in Remark 4.6, X ′ X' X ′ is unique up to isomorphism and, by Lemma 5.2, computable for quotients of strong nominal sets.
Algorithms and implementation. Building on this foundation, we develop efficient algorithms for equivalence checking, minimization, and active learning on strong nominal automata. By generalizing generating systems of register automata [28 , 29 ] to orbit-finite strong nominal sets, we obtain in Theorem 5.1 a language-equivalence algorithm that runs in polynomial time for a fixed alphabet dimension. Algorithms based on quotients, such as Moore’s minimization algorithm and active learning via ν L ∗ \nu L^* ν L ∗ [24 ] , are handled by strong approximations. For a fixed alphabet dimension, minimization stays polynomial in the orbit count; for active learning, only the equivalence-query count and observation-table cells do, while the total membership-query count remains factorial, as shown in Lemma 5.2 and Theorems 5.3 and 5.4.
We implemented the array representation and these algorithms in our library N a m a e \mathrm{Namae} Namae , and evaluated it in § 6 . We confirmed that N a m a e \mathrm{Namae} Namae outperforms the SMT-based tool N λ \mathrm{N}\lambda N λ and remains within a small constant factor of the dedicated register-automaton tool D E Q \mathrm{DEQ} DEQ , demonstrating the practical scalability of the array representation.
Contributions. We recast strong nominal sets , for which canonical minimization is known to fail, as an efficient foundation for nominal computation via the following contributions:
A categorical characterization of strong nominal sets , consolidating known and new equivalences into a single theorem (§ 3.1 ).
An array representation for orbit-finite strong nominal sets and equivariant maps between them, derived from the S N o m ≃ F a m ( Π o p ) \mathrm{SNom}\simeq\mathrm{Fam}(\Pi^{\mathrm{op}}) SNom ≃ Fam ( Π op ) equivalence (§ 3.2 ).
An existence theorem for projective covers , guaranteeing that every nominal set admits a strong approximation preserving its orbit count and dimensions (§ 4 ).
Concrete algorithms for language equivalence, minimization, and active learning on strong nominal automata, implemented in our library N a m a e \mathrm{Namae} Namae and evaluated (§ 5 and § 6 ).
Organization. § 2 recalls preliminaries; § 3 defines strong nominal sets, shows the four categorical equivalences, and develops the array representation; § 4 constructs projective covers, strong approximations, and strong lifts of automata; § 5 presents concrete algorithms with complexity bounds; § 6 evaluates our approach; § 7 discusses related work; and § 8 concludes. Omitted details appear in Appendices § 9 –§ 17 .
Preliminaries
We assume familiarity with group theory; our notation follows [9 , 40 ] . For a group G G G , we write g 1 g 2 g_1g_2 g 1 g 2 for the multiplication (applying g 2 g_2 g 2 first), i d \mathrm{id} id for the unit, and H ≤ G H\leq G H ≤ G for a subgroup H H H . For a set X X X , the symmetric group Sym ( X ) \operatorname{Sym}(X) Sym ( X ) consists of all permutations (bijections) of X X X . We write N \mathbb{N} N for the naturals and [ n ] = { 1 , … , n } [n] = \{1,\ldots,n\} [ n ] = { 1 , … , n } , and abbreviate the symmetric group on [ n ] [n] [ n ] as S n = Sym ( [ n ] ) S_n = \operatorname{Sym}([n]) S n = Sym ([ n ]) .
G-sets. A G G G -set X X X carries a group action ⋅ : G × X → X \cdot: G \times X \to X ⋅ : G × X → X . A map f : X → Y f: X \to Y f : X → Y between G G G -sets is equivariant if f ( g ⋅ x ) = g ⋅ f ( x ) f(g \cdot x) = g \cdot f(x) f ( g ⋅ x ) = g ⋅ f ( x ) , and a subset A ⊆ X A \subseteq X A ⊆ X is equivariant if g ⋅ A = A g \cdot A = A g ⋅ A = A for all g ∈ G g \in G g ∈ G . The orbit of x ∈ X x \in X x ∈ X is G ⋅ x = { g ⋅ x ∣ g ∈ G } G \cdot x = \{g \cdot x \mid g \in G\} G ⋅ x = { g ⋅ x ∣ g ∈ G } . We write orb ( X ) \operatorname{orb}(X) orb ( X ) for the set of orbits, so X = ⨆ O ∈ orb ( X ) O X = \bigsqcup_{O \in\operatorname{orb}(X)} O X = ⨆ O ∈ orb ( X ) O . A G G G -set X X X is transitive (or a single orbit ) if orb ( X ) \operatorname{orb}(X) orb ( X ) is a singleton.
Data symmetries and nominal sets. A data symmetry [9 ] is a pair S = ( A , G ) \mathcal{S} = (A, G) S = ( A , G ) of a countably infinite set A A A of atoms and a subgroup G ≤ Sym ( A ) G \leq\operatorname{Sym}(A) G ≤ Sym ( A ) . We focus on two symmetries: the equality symmetry E q = ( N , Sym ( N ) ) \mathsf{Eq} = (\mathbb{N}, \operatorname{Sym}(\mathbb{N})) Eq = ( N , Sym ( N )) and the total-order symmetry O r d = ( Q , Aut ( Q , < ) ) \mathsf{Ord} = (\mathbb{Q}, \operatorname{Aut}(\mathbb{Q}, <)) Ord = ( Q , Aut ( Q , < )) , where Aut ( Q , < ) \operatorname{Aut}(\mathbb{Q}, <) Aut ( Q , < ) comprises all order-preserving permutations.
For a finite set C ⊆ A C \subseteq A C ⊆ A , its pointwise stabilizer is Fix G ( C ) = { g ∈ G ∣ ∀ a ∈ C . g ( a ) = a } \operatorname{Fix}_{G}(C) = \{g \in G \mid\forall a \in C.\ g(a) = a\} Fix G ( C ) = { g ∈ G ∣ ∀ a ∈ C . g ( a ) = a } . We say C C C supports an element x x x of a G G G -set if Fix G ( C ) ⊆ Stab G ( x ) \operatorname{Fix}_{G}(C) \subseteq\operatorname{Stab}_{G}(x) Fix G ( C ) ⊆ Stab G ( x ) , where Stab G ( x ) = { g ∈ G ∣ g ⋅ x = x } \operatorname{Stab}_{G}(x) = \{g \in G \mid g \cdot x = x\} Stab G ( x ) = { g ∈ G ∣ g ⋅ x = x } is the stabilizer of x x x . A nominal set over S \mathcal{S} S is a G G G -set where every element has a finite support. We denote by N o m S \mathbf{Nom}_{\mathcal{S}} Nom S the category of nominal sets and equivariant maps, and by N o m S 1 \mathbf{Nom}_{\mathcal{S}}^{1} Nom S 1 its full subcategory of single-orbit nominal sets. A nominal set X X X is orbit-finite if orb ( X ) \operatorname{orb}(X) orb ( X ) is finite; we write N ( X ) = ∣ orb ( X ) ∣ N(X) = |\operatorname{orb}(X)| N ( X ) = ∣ orb ( X ) ∣ for its number of orbits. Over E q \mathsf{Eq} Eq and O r d \mathsf{Ord} Ord , orbit-finite nominal sets play the role of “finite” sets in nominal computation: they admit finite descriptions and are closed under equivariant subsets and finite products [9 ] .
Support and dimension. A data symmetry admits least supports if every element x x x in any nominal set has a unique least support supp ( x ) \operatorname{supp}(x) supp ( x ) . Both E q \mathsf{Eq} Eq and O r d \mathsf{Ord} Ord have this property [9 , 40 ] . The dimension of x x x is dim ( x ) = ∣ supp ( x ) ∣ \dim(x) = |\operatorname{supp}(x)| dim ( x ) = ∣ supp ( x ) ∣ . Since supp ( g ⋅ x ) = g ⋅ supp ( x ) \operatorname{supp}(g \cdot x) = g \cdot\operatorname{supp}(x) supp ( g ⋅ x ) = g ⋅ supp ( x ) , all elements of an orbit O O O share the same dimension, written dim ( O ) \dim(O) dim ( O ) ; for an orbit-finite set X X X we define dim ( X ) = max O ∈ orb ( X ) dim ( O ) \dim(X) = \max_{O \in\operatorname{orb}(X)} \dim(O) dim ( X ) = max O ∈ orb ( X ) dim ( O ) . The local symmetry of x x x is the restriction Stab G ( x ) ∣ supp ( x ) \operatorname{Stab}_{G}(x)|_{\operatorname{supp}(x)} Stab G ( x ) ∣ supp ( x ) of its stabilizer to its least support; it is a subgroup of Sym ( supp ( x ) ) \operatorname{Sym}(\operatorname{supp}(x)) Sym ( supp ( x )) , since every g ∈ Stab G ( x ) g \in\operatorname{Stab}_{G}(x) g ∈ Stab G ( x ) satisfies g ⋅ supp ( x ) = supp ( g ⋅ x ) = supp ( x ) g \cdot\operatorname{supp}(x) = \operatorname{supp}(g \cdot x) = \operatorname{supp}(x) g ⋅ supp ( x ) = supp ( g ⋅ x ) = supp ( x ) . When least supports exist, every single-orbit nominal set is determined up to isomorphism by a support representation ( C , S ) (C, S) ( C , S ) of a finite support C ⊆ A C \subseteq A C ⊆ A and a local symmetry group S ≤ Sym ( C ) S \leq\operatorname{Sym}(C) S ≤ Sym ( C ) [9 Prop. 9.15] .
Example 2.1. We illustrate these notions over E q \mathsf{Eq} Eq :
The set of atoms N \mathbb{N} N with action g ⋅ a = g ( a ) g \cdot a = g(a) g ⋅ a = g ( a ) is a single orbit (i.e., N ( N ) = 1 N(\mathbb{N}) = 1 N ( N ) = 1 ). Since supp ( a ) = { a } \operatorname{supp}(a) = \{a\} supp ( a ) = { a } , it has dimension 1 and trivial local symmetry.
A product X × Y X \times Y X × Y of nominal sets carries the pointwise action g ⋅ ( x , y ) = ( g ⋅ x , g ⋅ y ) g \cdot(x,y) = (g \cdot x, g \cdot y) g ⋅ ( x , y ) = ( g ⋅ x , g ⋅ y ) . Thus N 2 \mathbb{N}^{2} N 2 splits into two orbits: the diagonal { ( a , a ) ∣ a ∈ N } \{(a,a) \mid a \in\mathbb{N}\} {( a , a ) ∣ a ∈ N } of dimension 1, and the off-diagonal { ( a , b ) ∣ a ≠ b } \{(a,b) \mid a \ne b\} {( a , b ) ∣ a = b } of dimension 2. Both have trivial local symmetries.
The powerset of a nominal set has the action g ⋅ A = { g ⋅ a ∣ a ∈ A } g \cdot A = \{g \cdot a \mid a \in A\} g ⋅ A = { g ⋅ a ∣ a ∈ A } . The set of two-element subsets { { a , b } ∣ a ≠ b } \{\{a,b\} \mid a \ne b\} {{ a , b } ∣ a = b } forms a single orbit of dimension 2, with local symmetry Sym ( { a , b } ) ≅ S 2 \operatorname{Sym}(\{a,b\}) \cong S_{2} Sym ({ a , b }) ≅ S 2 swapping the atoms.
Any set X X X with trivial action g ⋅ x = x g \cdot x = x g ⋅ x = x is a nominal set with dimension 0.
Remark 2.2 (Local symmetry over E q \mathsf{Eq} Eq and O r d \mathsf{Ord} Ord ). Under E q \mathsf{Eq} Eq , a dimension-d d d element can carry any local symmetry S ≤ Sym ( [ d ] ) S \leq\operatorname{Sym}([d]) S ≤ Sym ([ d ]) ; under O r d \mathsf{Ord} Ord , local symmetries are always trivial [40 Lem. 5.1] , so each orbit is determined solely by its dimension. This triviality comes at the cost of more orbits: the set of d d d -tuples of distinct atoms, a single E q \mathsf{Eq} Eq -orbit of dimension d d d with trivial local symmetry, splits into d ! d! d ! O r d \mathsf{Ord} Ord -orbits when taken over the atoms Q \mathbb{Q} Q of O r d \mathsf{Ord} Ord . For example, the off-diagonal { ( a , b ) ∣ a ≠ b } \{(a,b) \mid a \ne b\} {( a , b ) ∣ a = b } , a single E q \mathsf{Eq} Eq -orbit, splits into { ( a , b ) ∣ a < b } \{(a,b) \mid a < b\} {( a , b ) ∣ a < b } and { ( a , b ) ∣ a > b } \{(a,b) \mid a > b\} {( a , b ) ∣ a > b } over O r d \mathsf{Ord} Ord .
Nominal automata. Fix an orbit-finite nominal set Σ \Sigma Σ as the input alphabet. The set Σ ∗ \Sigma^* Σ ∗ of finite words carries the pointwise action g ⋅ ( a 1 ⋯ a n ) = ( g ⋅ a 1 ) ⋯ ( g ⋅ a n ) g \cdot(a_1 \cdots a_n) = (g \cdot a_1) \cdots(g \cdot a_n) g ⋅ ( a 1 ⋯ a n ) = ( g ⋅ a 1 ) ⋯ ( g ⋅ a n ) ; an equivariant language is an equivariant subset L ⊆ Σ ∗ L \subseteq\Sigma^* L ⊆ Σ ∗ .
Definition 2.3 (nominal automaton). A (deterministic, orbit-finite) nominal automaton is a tuple A = ( Σ , Q , q 0 , δ , F ) \mathcal{A} = (\Sigma, Q, q_0, \delta, F) A = ( Σ , Q , q 0 , δ , F ) where Q Q Q is an orbit-finite nominal set of states, q 0 ∈ Q q_0 \in Q q 0 ∈ Q is an initial state with supp ( q 0 ) = ∅ \operatorname{supp}(q_0) = \varnothing supp ( q 0 ) = ∅ , δ : Q × Σ → Q \delta: Q \times\Sigma\to Q δ : Q × Σ → Q is an equivariant transition map, and F ⊆ Q F \subseteq Q F ⊆ Q is an equivariant set of accepting states.
The transition map extends to words by δ ∗ ( q , ε ) = q \delta^*(q, \varepsilon) = q δ ∗ ( q , ε ) = q and δ ∗ ( q , w a ) = δ ( δ ∗ ( q , w ) , a ) \delta^*(q, wa) = \delta(\delta^*(q, w), a) δ ∗ ( q , w a ) = δ ( δ ∗ ( q , w ) , a ) , and the language of A \mathcal{A} A is L ( A ) = { w ∈ Σ ∗ ∣ δ ∗ ( q 0 , w ) ∈ F } L(\mathcal{A}) = \{w \in\Sigma^* \mid\delta^*(q_0, w) \in F\} L ( A ) = { w ∈ Σ ∗ ∣ δ ∗ ( q 0 , w ) ∈ F } , which is an equivariant language. We call A \mathcal{A} A reachable if every state is of the form δ ∗ ( q 0 , w ) \delta^*(q_0, w) δ ∗ ( q 0 , w ) for some w ∈ Σ ∗ w \in\Sigma^* w ∈ Σ ∗ .
Nominal Myhill–Nerode theorem and minimal nominal automata. For an equivariant language L ⊆ Σ ∗ L \subseteq\Sigma^* L ⊆ Σ ∗ , the Myhill–Nerode equivalence is u ∼ L v ⟺ ∀ w ∈ Σ ∗ . ( u w ∈ L ⟺ v w ∈ L ) u \sim_L v \Longleftrightarrow\forall w \in\Sigma^*.\,(uw \in L \Longleftrightarrow vw \in L) u ∼ L v ⟺ ∀ w ∈ Σ ∗ . ( u w ∈ L ⟺ v w ∈ L ) . As ∼ L \sim_L ∼ L is equivariant, the quotient Σ ∗ / ∼ L \Sigma^*/\sim_L Σ ∗ / ∼ L is again a nominal set. The nominal Myhill–Nerode theorem [9 ] states that L L L is recognizable by a nominal automaton iff Σ ∗ / ∼ L \Sigma^*/\sim_L Σ ∗ / ∼ L is orbit-finite. In this case, the minimal nominal automaton A min \mathcal{A}_{\min} A m i n takes Σ ∗ / ∼ L \Sigma^*/\sim_L Σ ∗ / ∼ L as its states, with initial state [ ε ] L [\varepsilon]_L [ ε ] L , transitions δ min ( [ u ] L , a ) = [ u a ] L \delta_{\min}([u]_L, a) = [ua]_L δ m i n ([ u ] L , a ) = [ u a ] L , and accepting states { [ u ] L ∣ u ∈ L } \{[u]_L \mid u \in L\} {[ u ] L ∣ u ∈ L } . Among all nominal automata recognizing L L L , A min \mathcal{A}_{\min} A m i n simultaneously has the fewest state orbits and the smallest state dimension, as the reachable part of any such automaton maps onto it by an equivariant surjection, but its states may carry non-trivial local symmetries [9 Sec. 6.2] .
Categories and functors. We assume the basic vocabulary of category theory (see standard texts, e.g., [21 ] ) and use e : X ↠ Y e: X \twoheadrightarrow Y e : X ↠ Y for epimorphisms, m : Z ↪ X m: Z \hookrightarrow X m : Z ↪ X for monomorphisms, [ C , D ] [\mathcal{C}, \mathcal{D}] [ C , D ] for functor categories, and ∣ C ∣ |\mathcal{C}| ∣ C ∣ for the discrete category on the objects of C \mathcal{C} C . A functor is fully faithful if it is bijective on hom-sets, and an equivalence C ≃ D \mathcal{C} \simeq\mathcal{D} C ≃ D is a fully faithful, essentially surjective functor. An adjunction F ⊣ U : C ⇄ D F \dashv U: \mathcal{C} \rightleftarrows\mathcal{D} F ⊣ U : C ⇄ D induces a monad T = U F T = UF T = U F on D \mathcal{D} D ; we use its Eilenberg–Moore category EM ( T ) \operatorname{EM}(T) EM ( T ) of T T T -algebras and its Kleisli category Kl ( T ) \operatorname{Kl}(T) Kl ( T ) .
Free completions and projective objects. The free coproduct completion Fam ( C ) \operatorname{Fam}(\mathcal{C}) Fam ( C ) has objects ( A i ) i ∈ I (A_i)_{i \in I} ( A i ) i ∈ I (set-indexed families of C \mathcal{C} C -objects) and morphisms ( ρ , ( f i ) i ∈ I ) (\rho, (f_i)_{i \in I}) ( ρ , ( f i ) i ∈ I ) with ρ : I → J \rho: I \to J ρ : I → J and f i : A i → B ρ ( i ) f_i: A_i \to B_{\rho(i)} f i : A i → B ρ ( i ) . An object P P P is projective if morphisms P → Y P \to Y P → Y lift along epimorphisms X ↠ Y X \twoheadrightarrow Y X ↠ Y , and Proj ( C ) \operatorname{Proj}(\mathcal{C}) Proj ( C ) is the full subcategory of projective objects. A projective cover of X X X is a pair ( P , e ) (P,e) ( P , e ) of a projective object P P P and a superfluous epimorphism e : P ↠ X e: P \twoheadrightarrow X e : P ↠ X , meaning e e e restricted to any proper subobject of P P P is no longer an epimorphism.
Nominal sets and the functor category [ [ I , S e t ] ] [\![\mathbb{I}, \mathbf{Set}]\!] [ [ I , Set ] ] . Let I \mathbb{I} I denote the category of finite subsets of N \mathbb{N} N and injections. It is established [20 , 33 ] that there is an adjunction F ⊣ U : N o m E q ⇄ [ [ I , S e t ] ] F \dashv U: \mathbf{Nom}_{\mathsf{Eq}} \rightleftarrows[\![\mathbb{I}, \mathbf{Set}]\!] F ⊣ U : Nom Eq ⇄ [ [ I , Set ] ] with U ( X ) ( C ) = { x ∈ X ∣ supp ( x ) ⊆ C } U(X)(C) = \{x \in X \mid\operatorname{supp}(x) \subseteq C\} U ( X ) ( C ) = { x ∈ X ∣ supp ( x ) ⊆ C } and F ( Y ) = ∐ C Y ( C ) × Inj ( C , N ) F(Y) = \coprod_C Y(C) \times\operatorname{Inj}(C,\mathbb{N}) F ( Y ) = ∐ C Y ( C ) × Inj ( C , N ) . The induced monad T = U F T = UF T = U F has EM ( T ) ≃ [ [ I , S e t ] ] \operatorname{EM}(T) \simeq[\![\mathbb{I}, \mathbf{Set}]\!] EM ( T ) ≃ [ [ I , Set ] ] . The comparison functor J : N o m E q → [ [ I , S e t ] ] J: \mathbf{Nom}_{\mathsf{Eq}} \to[\![\mathbb{I}, \mathbf{Set}]\!] J : Nom Eq → [ [ I , Set ] ] , J ( X ) ( C ) = { x ∈ X ∣ supp ( x ) ⊆ C } J(X)(C) = \{x \in X \mid\operatorname{supp}(x) \subseteq C\} J ( X ) ( C ) = { x ∈ X ∣ supp ( x ) ⊆ C } , is fully faithful but not essentially surjective [20 , 33 ] , embedding N o m E q \mathbf{Nom}_{\mathsf{Eq}} Nom Eq as a full subcategory of the functor category [ [ I , S e t ] ] [\![\mathbb{I}, \mathbf{Set}]\!] [ [ I , Set ] ] .
Strong Nominal Sets
This section introduces strong nominal sets : nominal sets with trivial local symmetries, hence computationally lightweight. We fix a data symmetry S = ( A , G ) \mathcal{S} = (A, G) S = ( A , G ) admitting least supports.
Definition 3.1 (strong support and strong nominal sets). Let x x x be an element of a nominal set X X X with least support C = supp ( x ) C = \operatorname{supp}(x) C = supp ( x ) . We say C C C strongly supports x x x if Stab G ( x ) ⊆ Fix G ( C ) \operatorname{Stab}_{G}(x) \subseteq\operatorname{Fix}_{G}(C) Stab G ( x ) ⊆ Fix G ( C ) , i.e., Stab G ( x ) = Fix G ( C ) \operatorname{Stab}_{G}(x) = \operatorname{Fix}_{G}(C) Stab G ( x ) = Fix G ( C ) , as Fix G ( C ) ⊆ Stab G ( x ) \operatorname{Fix}_{G}(C) \subseteq\operatorname{Stab}_{G}(x) Fix G ( C ) ⊆ Stab G ( x ) holds because C C C supports x x x . A nominal set X X X is strong if every element is strongly supported by its least support.
We write SNom S _{\mathrm{S}} S for the full subcategory of Nom S _{\mathrm{S}} S on the strong nominal sets, and SNom S 1 _{\mathrm{S}}^{1} S 1 for its full subcategory of single-orbit strong nominal sets. Strong support was originally introduced in nominal game semantics to ensure well-defined strategy composition [31 , 37 , 38 ] , there defined for an arbitrary finite supporting set. A few of its categorical properties were briefly noted in the literature [20 , 33 ] .
Example 3.2. Over Eq, the atoms N \mathbb{N} N and the product N 2 \mathbb{N}^{2} N 2 from Example 2.1 are strong. The set { { a , b } ∣ a ≠ b } \{\{a,b\} \mid a \ne b\} {{ a , b } ∣ a = b } is not strong: the swap ( a b ) (a\ b) ( a b ) satisfies ( a b ) ⋅ { a , b } = { a , b } (a\ b) \cdot\{a,b\} = \{a,b\} ( a b ) ⋅ { a , b } = { a , b } . Its ordered counterpart { ( a , b ) ∣ a ≠ b } \{(a,b) \mid a \ne b\} {( a , b ) ∣ a = b } has the same dimension and orbit count, but is strong. More generally, every polynomial orbit-finite (pof) set N n 1 + ⋯ + N n k \mathbb{N}^{n_{1}} + \cdots+ \mathbb{N}^{n_{k}} N n 1 + ⋯ + N n k [7 Def. 1.1] is strong, but not conversely: up to isomorphism, the orbit-finite strong nominal sets are exactly the equivariant subsets of pof sets. For instance, the off-diagonal { ( a , b ) ∣ a ≠ b } ⊊ N 2 \{(a,b) \mid a \ne b\} \subsetneq\mathbb{N}^{2} {( a , b ) ∣ a = b } ⊊ N 2 is strong but is a proper equivariant subset, not a pof set itself.
As suggested above, strong support is inherently tied to the triviality of local symmetries.
Proposition 3.3 (local-symmetry characterization). A nominal set X X X is strong if and only if every element x ∈ X x \in X x ∈ X has trivial local symmetry, i.e., Stab G ( x ) ∣ supp ( x ) = { id } \operatorname{Stab}_{G}(x)|_{\operatorname{supp}(x)} = \{\operatorname{id}\} Stab G ( x ) ∣ supp ( x ) = { id } .
Recall that a single-orbit nominal set is determined up to isomorphism by a support representation ( C , S ) (C,S) ( C , S ) . For strong nominal sets, S = { id } S = \{\operatorname{id}\} S = { id } , meaning orbits are uniquely determined by their dimension ∣ C ∣ |C| ∣ C ∣ . Over Ord, local symmetries are always trivial [40 Lem. 5.1] , hence SNom O r d _{\mathrm{Ord}} Ord = Nom O r d _{\mathrm{Ord}} Ord .
Categorical Characterization
From now on, we fix S = E q \mathcal{S} = \mathrm{Eq} S = Eq and drop it from the notation. Recall that Nom is equivalent to the Schanuel topos Sh ( I o p ) \operatorname{Sh}(\mathbb{I}^{\mathrm{op}}) Sh ( I op ) (sheaves for the atomic topology) and to the category NSet I _{\mathbb{I}} I of named sets with symmetries , where elements carry permutation groups [14 , 16 , 34 ] ; the notation NSet I _{\mathbb{I}} I follows [36 Sec. 5.1] . The subcategory SNom admits an analogous but simpler description where all local symmetry groups are trivial.
Theorem 3.4 (categorical characterization of strong nominal sets). Let T = U F T = UF T = U F be the monad on [ [ I ] , S e t ] [[\mathbb{I}], \mathbf{Set}] [[ I ] , Set ] induced by the adjunction F ⊣ U : N o m ⇄ [ [ I ] , S e t ] F \dashv U \colon\mathbf{Nom} \rightleftarrows[[\mathbb{I}], \mathbf{Set}] F ⊣ U : Nom ⇄ [[ I ] , Set ] of Section 2. Then, there are equivalences of categories
S N o m ≃ K l ( T ) ≃ F a m ( I o p ) ≃ P r o j ( [ I , S e t ] ) ≃ N S e t f n , \mathbf{SNom} \simeq\mathbf{Kl}(T) \simeq\mathbf{Fam}(\mathbb{I}^{\mathrm{op}}) \simeq\mathbf{Proj}([\mathbb{I}, \mathbf{Set}]) \simeq\mathbf{NSet}_{\mathrm{fn}}, SNom ≃ Kl ( T ) ≃ Fam ( I op ) ≃ Proj ([ I , Set ]) ≃ NSet fn , where NSet f n _{\mathrm{fn}} fn is the category of finitely named sets [25 ] : sets whose elements each carry a finite name set, related by injective renamings, as detailed in Appendix B.4.
We prove these in Appendix B; the sequel builds on Fam ( I o p ) \operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) Fam ( I op ) and Proj ( [ I , S e t ] ) \operatorname{Proj}([\mathbb{I},\mathbf{Set}]) Proj ([ I , Set ]) , while the other two equivalences relate SNom to prior frameworks:
SNom ≃ Kl ( T ) \simeq\operatorname{Kl}(T) ≃ Kl ( T ) identifies SNom with the free T T T -algebras [20 , 33 ] , as depicted in Figure 2 .
SNom ≃ Fam ( I o p ) \simeq\operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) ≃ Fam ( I op ) underlies the array representation of Section 3.2 via S N o m 1 ≃ I o p \mathbf{SNom}^{1} \simeq\mathbb{I}^{\mathrm{op}} SNom 1 ≃ I op .
SNom ≃ Proj ( [ I , S e t ] ) \simeq\operatorname{Proj}([\mathbb{I},\mathbf{Set}]) ≃ Proj ([ I , Set ]) provides the correct setting for the projective covers of Section 41 .
SNom ≃ N S e t f n \simeq\mathbf{NSet}_{\mathrm{fn}} ≃ NSet fn links SNom to the early named-set development [25 ] .
Figure 2. The categorical relationship between SNom, Nom, and [ I , S e t ] [\mathbb{I}, \mathbf{Set}] [ I , Set ] .
Data Representations
From the equivalence SNom ≃ Fam ( I o p ) \simeq\operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) ≃ Fam ( I op ) of Theorem 3.4, we derive a concrete, constraint-free representation of data and equivariant maps, the basis of our implementation in Section 6. It is the E q \mathbf{Eq} Eq counterpart of the sorted array representation for NomOrd [40 ] : since S N o m O r d = N o m O r d \mathbf{SNom}_{\mathrm{Ord}} = \mathbf{NomOrd} SNom Ord = NomOrd , theirs covers all of NomOrd , whereas ours captures precisely the strong nominal sets.
Array representation. Under S N o m 1 ≃ I o p \mathbf{SNom}^{1} \simeq\mathbb{I}^{\mathrm{op}} SNom 1 ≃ I op , a single-orbit strong nominal set is isomorphic to Inj ( C , N ) \operatorname{Inj}(C,\mathbb{N}) Inj ( C , N ) for a finite set C C C . Choosing C = [ d ] C = [d] C = [ d ] , we identify the orbit with its dimension d d d , and an element with an injection [ d ] ↪ N [d] \hookrightarrow\mathbb{N} [ d ] ↪ N , i.e., a tuple of d d d distinct atoms ⟨ a 1 , … , a d ⟩ \langle a_{1}, \ldots, a_{d}\rangle ⟨ a 1 , … , a d ⟩ . By SNom ≃ Fam ( I o p ) \simeq\operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) ≃ Fam ( I op ) , any orbit-finite strong nominal set X ≅ ∐ i ∈ I Inj ( [ d i ] , N ) X \cong\coprod_{i \in I} \operatorname{Inj}([d_{i}],\mathbb{N}) X ≅ ∐ i ∈ I Inj ([ d i ] , N ) is determined by a finite list of dimensions ( d i ) i ∈ I (d_{i})_{i \in I} ( d i ) i ∈ I , with elements represented as pairs ( i , ⟨ a 1 , … , a d i ⟩ ) (i,\langle a_{1}, \ldots, a_{d_{i}}\rangle) ( i , ⟨ a 1 , … , a d i ⟩) . We call this the array representation . Unlike over Ord, where elements are uniquely determined by their least supports as sorted arrays [40 ] , an element over Eq is an arbitrary array of d d d distinct atoms: its least support is the set of its entries, and the array additionally fixes their order.
Equivariant maps are similarly concrete. An equivariant map Inj ( [ m ] , N ) → Inj ( [ n ] , N ) \operatorname{Inj}([m],\mathbb{N}) \to\operatorname{Inj}([n],\mathbb{N}) Inj ([ m ] , N ) → Inj ([ n ] , N ) is precomposition with a unique injection h : [ n ] ↪ [ m ] h\colon[n] \hookrightarrow[m] h : [ n ] ↪ [ m ] , mapping elements via ⟨ a 1 , … , a m ⟩ ↦ ⟨ a h ( 1 ) , … , a h ( n ) ⟩ \langle a_{1}, \ldots, a_{m}\rangle\mapsto\langle a_{h(1)}, \ldots, a_{h(n)}\rangle ⟨ a 1 , … , a m ⟩ ↦ ⟨ a h ( 1 ) , … , a h ( n ) ⟩ . Generally, an equivariant map is represented by assigning each source orbit a target orbit and an index array ⟨ h ( 1 ) , … , h ( n ) ⟩ \langle h(1), \ldots, h(n)\rangle ⟨ h ( 1 ) , … , h ( n )⟩ . Consequently, both elements and functions are represented as finite integer arrays.
Connection to register automata. This array representation concretely matches the configuration spaces of register automata with injective (possibly partial) register assignments [9 , 17 ] . A configuration consisting of a state q q q and an assignment of d q d_{q} d q distinct atoms naturally forms an element ( q , ⟨ a 1 , … , a d q ⟩ ) ∈ ∐ q ∈ Q Inj ( [ d q ] , N ) (q,\langle a_{1}, \ldots, a_{d_{q}}\rangle) \in\coprod_{q \in Q} \operatorname{Inj}([d_{q}],\mathbb{N}) ( q , ⟨ a 1 , … , a d q ⟩) ∈ ∐ q ∈ Q Inj ([ d q ] , N ) , which is an element of an orbit-finite strong nominal set. For instance, the configuration space of Figure 1 forms a strong nominal set with three orbits: no open resources ( q 0 , ⟨ ⟩ ) (q_{0},\langle\rangle) ( q 0 , ⟨ ⟩) , one ( q 1 , ⟨ a ⟩ ) (q_{1},\langle a\rangle) ( q 1 , ⟨ a ⟩) , and two ( q 2 , ⟨ a , b ⟩ ) (q_{2},\langle a,b\rangle) ( q 2 , ⟨ a , b ⟩) . Thus, register-automaton configurations are not merely nominal, but strong nominal sets , naturally justifying their array representation; cf. the closely related observation for P D R A s \mathrm{PDRA}s PDRA s [3 Rem. 6] .
Products. Products have a less transparent orbit structure, as they mix atoms from two factors. For single orbits X X X and Y Y Y of dimensions m m m and n n n , a pair ( ⟨ a 1 , … , a m ⟩ , ⟨ b 1 , … , b n ⟩ ) (\langle a_{1}, \ldots, a_{m}\rangle,\langle b_{1}, \ldots, b_{n}\rangle) (⟨ a 1 , … , a m ⟩ , ⟨ b 1 , … , b n ⟩) is classified up to the G G G -action by its shared atoms, captured by the relation ( i , j ) ∈ π ⟺ a i = b j (i,j) \in\pi\Longleftrightarrow a_{i} = b_{j} ( i , j ) ∈ π ⟺ a i = b j ; distinctness on each side makes π \pi π a partial bijection π : [ m ] ⇀ [ n ] \pi\colon[m] \rightharpoonup[n] π : [ m ] ⇀ [ n ] . Thus, the orbits of X × Y X \times Y X × Y correspond bijectively to the partial bijections [ m ] ⇀ [ n ] [m] \rightharpoonup[n] [ m ] ⇀ [ n ] , where the orbit for π \pi π has dimension m + n − ∣ dom ( π ) ∣ m+n-\lvert\operatorname{dom}(\pi)\rvert m + n − ∣ dom ( π )∣ ; this specializes the product representations of [9 Sec. 10.3] [12 Sec. 5] to strong nominal sets, with [40 Sec. 5.3] as the Ord analogue. Each such orbit is itself strong, so strong nominal sets are closed under finite products. Counting these partial bijections yields the number of product orbits:
Proposition 3.5 (number of product orbits). Let X X X and Y Y Y be single strong orbits of dimensions m m m and n n n . The number of orbits of X × Y X \times Y X × Y equals the number of partial bijections, that is,
N ( X × Y ) = ∑ k = 0 min ( m , n ) ( m k ) ( n k ) k ! . N(X \times Y) = \sum_{k=0}^{\min(m,n)} \binom{m}{k}\binom{n}{k} k!. N ( X × Y ) = k = 0 ∑ m i n ( m , n ) ( k m ) ( k n ) k ! . This count grows factorially in min ( m , n ) \min(m,n) min ( m , n ) , a combinatorial blow-up that dominates the costs of the algorithms of § 5 , which enumerate these orbits.
Effective operations. The array representation renders standard nominal operations effective. In practice, we manipulate orbit-finite strong nominal sets, typically presented as equivariant subsets. They are closed under the following operations:
union X ∪ Y X \cup Y X ∪ Y and intersection X ∩ Y X \cap Y X ∩ Y within a common strong nominal set;
coproduct X ⊔ Y X \sqcup Y X ⊔ Y and finite product X × Y X \times Y X × Y ;
image { f ( x ) ∣ x ∈ X } \{f(x) \mid x \in X\} { f ( x ) ∣ x ∈ X } along an equivariant map f : X → Y f : X \to Y f : X → Y ;
filtering { x ∈ X ∣ p ( x ) } \{x \in X \mid p(x)\} { x ∈ X ∣ p ( x )} by an equivariant predicate p : X → { 0 , 1 } p : X \to\{0,1\} p : X → { 0 , 1 } .
Furthermore, the representation supports basic decision and inspection primitives:
checking membership x ∈ X x \in X x ∈ X , inclusion Y ⊆ X Y \subseteq X Y ⊆ X , and emptiness X = ∅ X = \varnothing X = ∅ ;
enumerating orbits and selecting representative elements.
Appendix F details the worst-case costs of all these operations.
Projective Covers
Unlike the operations in § 3.2 , quotients fall outside the class of strong nominal sets.
Example 4.1 (strong nominal sets are not closed under quotients). Recall from Example 3.2 that the off-diagonal X = { ( a , b ) ∣ a ≠ b } X = \{(a,b) \mid a \ne b\} X = {( a , b ) ∣ a = b } is a strong single orbit. Consider the equivalence relation
R = { ( ( a , b ) , ( a , b ) ) ∣ a ≠ b } ∪ { ( ( a , b ) , ( b , a ) ) ∣ a ≠ b } . R = \{((a,b),(a,b)) \mid a \ne b\} \cup\{((a,b),(b,a)) \mid a \ne b\}. R = {(( a , b ) , ( a , b )) ∣ a = b } ∪ {(( a , b ) , ( b , a )) ∣ a = b } . which identifies ( a , b ) (a,b) ( a , b ) with its swap ( b , a ) (b,a) ( b , a ) , so that its classes are the unordered pairs { a , b } \{a,b\} { a , b } . As an equivariant subset of X × X X \times X X × X , the relation R R R is strong. However, as noted in Example 3.2 , the quotient X / R ≅ { { a , b } ∣ a ≠ b } X/R \cong\{\{a,b\} \mid a \ne b\} X / R ≅ {{ a , b } ∣ a = b } is not strong.
Quotients are unavoidable in automata theory: the minimal automaton’s state space Σ ∗ / ∼ L \Sigma^*/{\sim_L} Σ ∗ / ∼ L typically falls outside SNom; for the running example Res(2), the Myhill–Nerode classes with two open resources are exactly these unordered pairs, as observed in § 1 . To compute with such objects in the array representation, we approximate them using projective covers . We develop this notion in § 4.1 and apply it to automata in § 4.2 .
Projective Covers as Strong Approximation
By Theorem 3.4 , the functor J ′ = J O : S N o m → [ I , S e t ] J' = J_{\mathcal{O}} : \mathrm{SNom} \to[\mathbb{I}, \mathbf{Set}] J ′ = J O : SNom → [ I , Set ] identifies SNom with Proj ( [ I , S e t ] ) \operatorname{Proj}([\mathbb{I}, \mathbf{Set}]) Proj ([ I , Set ]) . This projectivity already makes strong nominal sets convenient domains, as maps from them lift along epimorphisms. Moreover, projective covers always exist:
Theorem 4.2 (projective cover existence). Every object F ∈ [ I , S e t ] \mathcal{F} \in[\mathbb{I}, \mathbf{Set}] F ∈ [ I , Set ] admits a projective cover ( J ′ ( X ′ ) , e ) (J'(X'), e) ( J ′ ( X ′ ) , e ) with a strong nominal set X ′ X' X ′ and a superfluous epimorphism e : J ′ ( X ′ ) → F e : J'(X') \to\mathcal{F} e : J ′ ( X ′ ) → F .
We provide an explicit construction in Appendix D. Being projective with a superfluous epimorphism, J ′ ( X ′ ) J'(X') J ′ ( X ′ ) is a retract of every projective object mapping onto F \mathcal{F} F , so it approximates F \mathcal{F} F optimally. When applied to J ( X ) J(X) J ( X ) for X ∈ N o m X \in\mathbf{Nom} X ∈ Nom , full faithfulness of J J J yields a unique equivariant map p : X ′ → X p: X' \to X p : X ′ → X with J ( p ) = e J(p) = e J ( p ) = e , and since e e e is a pointwise epimorphism, p p p is an equivariant surjection. This p p p induces a surjective map orb ( p ) : orb ( X ′ ) ↠ orb ( X ) \operatorname{orb}(p): \operatorname{orb}(X') \twoheadrightarrow\operatorname{orb}(X) orb ( p ) : orb ( X ′ ) ↠ orb ( X ) on orbits. Crucially, the projective cover merges no orbits and inflates no dimensions:
Theorem 4.3 (orbit-count preservation). Let X ∈ N o m X \in\mathbf{Nom} X ∈ Nom and let p : X ′ ↠ X p: X' \twoheadrightarrow X p : X ′ ↠ X be the equivariant surjection corresponding to the projective cover of J ( X ) J(X) J ( X ) , as above. Then, orb ( p ) \operatorname{orb}(p) orb ( p ) is a dimension-preserving bijection, i.e., dim ( O ′ ) = dim ( orb ( p ) ( O ′ ) ) \dim(O') = \dim(\operatorname{orb}(p)(O')) dim ( O ′ ) = dim ( orb ( p ) ( O ′ )) for every orbit O ′ O' O ′ of X ′ X' X ′ .
By Appendix D, the projective cover is unique up to isomorphism, so we call X ′ X' X ′ the strong approximation of X X X . Intuitively, p p p strips local symmetries from X X X without merging orbits or inflating dimensions; the discarded symmetry is recorded in the kernel pair of p p p . For instance, the non-strong orbit X = { { a , b } ∣ a ≠ b } X = \{\{a,b\} \mid a \ne b\} X = {{ a , b } ∣ a = b } has the strong approximation X ′ = { ( a , b ) ∣ a ≠ b } X' = \{(a,b) \mid a \ne b\} X ′ = {( a , b ) ∣ a = b } with p ( a , b ) = { a , b } p(a,b) = \{a,b\} p ( a , b ) = { a , b } . Since orb ( p ) \operatorname{orb}(p) orb ( p ) is bijective, X X X is orbit-finite iff X ′ X' X ′ is, with N ( X ′ ) = N ( X ) N(X') = N(X) N ( X ′ ) = N ( X ) ; the existence of such a surjection is essentially [9 Cor. 4.14] , applied orbit by orbit.
Strong Lifts of the Minimal Nominal Automaton
By combining projectivity with the orbit-count preservation of Theorem 4.3, we transform any nominal automaton into a language-equivalent strong automaton with the same orbit count and dimensions, which we call a strong lift . We say a nominal automaton is strong if its alphabet and state space are both strong nominal sets. Throughout, we assume the alphabet Σ \Sigma Σ is strong, i.e., a strong nominal set, and call it a strong alphabet ; this holds for typical data alphabets such as tuples of pairwise distinct atoms.
Theorem 4.4 (strong lifts of automata). Let A = ( Σ , Q , q 0 , δ , F ) \mathcal{A} = (\Sigma, Q, q_0, \delta, F) A = ( Σ , Q , q 0 , δ , F ) be a nominal automaton over a strong alphabet Σ \Sigma Σ , and let p : Q ′ ↠ Q p: Q' \twoheadrightarrow Q p : Q ′ ↠ Q be the equivariant surjection corresponding to the projective cover of J ( Q ) J(Q) J ( Q ) . Then, there exists a strong nominal automaton A ′ = ( Σ , Q ′ , q 0 ′ , δ ′ , F ′ ) \mathcal{A}' = (\Sigma, Q', q'_0, \delta', F') A ′ = ( Σ , Q ′ , q 0 ′ , δ ′ , F ′ ) for which p p p is an automaton homomorphism, that is, p ( q 0 ′ ) = q 0 p(q'_0) = q_0 p ( q 0 ′ ) = q 0 , F ′ = p − 1 ( F ) F' = p^{-1}(F) F ′ = p − 1 ( F ) , and p ( δ ′ ( q ′ , σ ) ) = δ ( p ( q ′ ) , σ ) p(\delta'(q', \sigma)) = \delta(p(q'), \sigma) p ( δ ′ ( q ′ , σ )) = δ ( p ( q ′ ) , σ ) for all q ′ ∈ Q ′ q' \in Q' q ′ ∈ Q ′ and σ ∈ Σ \sigma\in\Sigma σ ∈ Σ ; in particular, L ( A ′ ) = L ( A ) L(\mathcal{A}') = L(\mathcal{A}) L ( A ′ ) = L ( A ) .
Proof sketch. Since Theorem 4.2 ensures Q ′ Q' Q ′ is strong and Σ \Sigma Σ is strong by assumption, J ′ ( Q ′ × Σ ) J'(Q' \times\Sigma) J ′ ( Q ′ × Σ ) is projective by Theorem 3.4 , so the map δ ∘ ( p × id Σ ) \delta\circ(p \times\operatorname{id}_\Sigma) δ ∘ ( p × id Σ ) lifts along p p p via projectivity; furthermore, Theorem 4.3 dictates that q 0 ′ q'_0 q 0 ′ is the unique dimension-0 element in the pre-image of q 0 q_0 q 0 , and we set F ′ = p − 1 ( F ) F' = p^{-1}(F) F ′ = p − 1 ( F ) . Full details appear in Appendix E.
Consequently, by Theorem 4.3, orb ( p ) \operatorname{orb}(p) orb ( p ) is a dimension-preserving bijection, so Q ′ Q' Q ′ inherits the orbit structure of Q Q Q . Specializing to the minimal automaton yields our main result:
Corollary 4.5 (strong lift of the minimal nominal automaton). For a strong alphabet Σ \Sigma Σ , every equivariant language L ⊆ Σ ∗ L \subseteq\Sigma^* L ⊆ Σ ∗ recognized by a nominal automaton is also recognized by a strong nominal automaton whose state set has the same orbit count and dimensions as the minimal nominal automaton A min \mathcal{A}_{\min} A m i n of L L L .
Remark 4.6 (relation to register automata). Corollary 4.5 can be assembled from known results: combining the least-support-preserving surjections of [9 Cor. 4.14] with the transition-lifting lemma [9 Lem. 6.7] yields what we call a strong lift of the minimal automaton (a similar statement and observation appeared in [6 Lem. 6.9] and [3 ] ). Our contribution is to identify the structure behind these constructions as the projective cover: the resulting state space is exactly the strong approximation of the minimal one, unique up to isomorphism and, crucially for Section 5, computable for quotients of strong nominal sets by Lemma 5.2.
However, strong lifts are not canonical: the lifted transition δ ′ \delta' δ ′ is generally non-unique (per domain transition orbit, the valid choices of δ ′ \delta' δ ′ into a target orbit with local symmetry group H H H are in bijection with H H H ). A further cost is that the domain Q ′ × Σ Q' \times\Sigma Q ′ × Σ may contain more orbits than Q × Σ Q \times\Sigma Q × Σ , as local symmetries that previously fused transition orbits are removed (e.g., the two Close transitions from q 2 q_2 q 2 in Figure 1 form a single orbit in the minimal automaton). Figure 3 illustrates both: a non-strong self-loop on input { a , b } \{a,b\} { a , b } with local symmetry S 2 S_2 S 2 (left) yields four possible projective-cover lifts (right). Stripping S 2 S_2 S 2 splits the single transition orbit into two, each with two valid target choices. This non-uniqueness was already observed in [5 , 9 ] , where transitions are lifted via per-orbit representative choices; in our formulation, the valid lifts differ exactly by the discarded local symmetries, recorded in the kernel pair of p p p .
Figure 3. Non-uniqueness of strong lifts. The non-strong transition (left) has four projective-cover lifts (right): two uniform (top) and two mixed (bottom), whose targets share an orbit (dotted).
This orbit inflation is the deliberate price of enforcing trivial local symmetries; as our experiments show in § 6 , the computational savings of the constraint-free array representation of § 3.2 far outweigh this overhead.
Automata Algorithms
We translate the developments of § 4 into algorithms. § 5.1 presents a language-equivalence check for strong nominal automata that runs in polynomial time for a fixed alphabet dimension, generalizing the register-automaton equivalence algorithm [28 ] . § 5.2 addresses minimization and learning via a quotient operation that computes the strong approximation of the quotient by the Myhill–Nerode equivalence; this operation is polynomial in the orbit count but, by Proposition 3.5 , factorial in the dimension. All algorithms are implemented in our library Namae and evaluated in § 6 .
Computational model. All inputs (automata and alphabets) are presented in the array representation of § 3.2 , hence strong, and we measure algorithmic cost by the number of orbits N ( X ) N(X) N ( X ) and the dimension dim ( X ) \dim(X) dim ( X ) ; this loses no generality, as Theorem 4.4 provides language-equivalent strong lifts preserving both measures. We assume orbit-level primitives (mapping an element to its orbit, comparing two orbits, selecting a representative) take constant time, as in [40 Sec. 8] ; Appendix § 14 details the costs of the effective operations under this assumption. Two extra quantities appear in the algorithmic costs: μ ( d ) \mu(d) μ ( d ) bounds the cost of Schreier–Sims operations on a subgroup of S d S_d S d (polynomial in d d d ) [15 ] ; and β ( m , n ) \beta(m,n) β ( m , n ) is the number of partial bijections [ m ] ⇀ [ n ] [m] \rightharpoonup[n] [ m ] ⇀ [ n ] , i.e., the product-orbit count of Proposition 3.5 . For a fixed n n n , β ( m , n ) = Θ ( m n ) \beta(m,n)=\Theta(m^n) β ( m , n ) = Θ ( m n ) is polynomial in m m m , whereas β ( d , d ) = O ( 2 d d ! ) \beta(d,d)=O(2^d d!) β ( d , d ) = O ( 2 d d !) grows factorially.
Language Equivalence
Let A 1 \mathcal{A}_1 A 1 and A 2 \mathcal{A}_2 A 2 be strong nominal automata with state spaces Q 1 Q_1 Q 1 and Q 2 Q_2 Q 2 , and suppose we wish to decide whether L ( A 1 ) = L ( A 2 ) L(\mathcal{A}_1)=L(\mathcal{A}_2) L ( A 1 ) = L ( A 2 ) . Since the automata are deterministic, language equivalence coincides with bisimilarity. This can be decided by a breadth-first search over Q 1 × Q 2 Q_1 \times Q_2 Q 1 × Q 2 starting from the initial states. Naively, this requires exploring all orbits of Q 1 × Q 2 Q_1 \times Q_2 Q 1 × Q 2 in the worst case; by Proposition 3.5 , this number grows factorially with the dimension (i.e., β ( d , d ) = O ( 2 d d ! ) \beta(d,d)=O(2^d d!) β ( d , d ) = O ( 2 d d !) ).
To overcome this, we employ a generating system G \mathcal{G} G , the core data structure behind the polynomial-time equivalence check for register automata [28 ] , which originates in the group-theoretic representation of bisimulations [27 , 30 ] and is implemented in DEQ [29 ] . Since register-automaton configurations form strong nominal sets, as § 3.2 shows, this data structure naturally generalizes to our setting.2 The generating system maintains an equivariant equivalence relation ∼ \sim ∼ on a strong nominal set X X X (here, X = Q 1 ⊔ Q 2 X=Q_1 \sqcup Q_2 X = Q 1 ⊔ Q 2 ), using time and space polynomial in both the orbit count and the dimension. Its efficiency comes from how each equivalence class is stored: by a single orbit together with generators of its symmetry group (a subgroup of S d S_d S d ), rather than explicitly listing all related pairs in X × X X \times X X × X . It supports four operations, summarized in Table 1 ; Appendix § 15 gives the aggregate analysis.
Table 1. Operations of the generating system G \mathcal{G} G and their worst-case per-call costs.
This generalization is correct: G \mathcal{G} G always represents an equivariant equivalence relation, after any sequence of merges it maintains the finest one relating the merged pairs, and classes returns exactly the strong approximation of the quotient together with its lift. The complexity is given by the following theorem (correctness, pseudocode, and proofs in Appendix § 15 ).
Theorem 5.1 (language equivalence). Let A 1 \mathcal{A}_1 A 1 and A 2 \mathcal{A}_2 A 2 be strong nominal automata with state spaces Q 1 Q_1 Q 1 and Q 2 Q_2 Q 2 over a common strong alphabet Σ \Sigma Σ , with N = N ( Q 1 ) + N ( Q 2 ) N=N(Q_1)+N(Q_2) N = N ( Q 1 ) + N ( Q 2 ) , d = dim ( Q 1 ⊔ Q 2 ) d=\dim(Q_1 \sqcup Q_2) d = dim ( Q 1 ⊔ Q 2 ) , and e = dim ( Σ ) e=\dim(\Sigma) e = dim ( Σ ) . Their language equivalence is decidable in time
O ( N ⋅ d 2 ⋅ N ( Σ ) ⋅ β ( 2 d , e ) ⋅ μ ( d ) + N 2 d ) , O(N \cdot d^2 \cdot N(\Sigma) \cdot\beta(2d,e) \cdot\mu(d)+N^2d), O ( N ⋅ d 2 ⋅ N ( Σ ) ⋅ β ( 2 d , e ) ⋅ μ ( d ) + N 2 d ) , which, for a fixed alphabet dimension e e e , is polynomial in N N N , N ( Σ ) N(\Sigma) N ( Σ ) , and d d d .
This generalizes the polynomial-time result for register automata [28 ] to strong nominal automata, and gives a more precise complexity bound in terms of N N N and d d d .
Minimization and Learning
Both minimization and learning rely on quotienting by the Myhill–Nerode equivalence. Since Example 4.1 demonstrates that strong nominal sets are not closed under quotients, we instead compute the strong approximation of the quotient via the generating system introduced in § 5.1 , formalized by the following lemma (pseudocode and proof in Appendix § 16 ).
Lemma 5.2 (quotient). Let X X X be an orbit-finite strong nominal set with d = dim ( X ) d = \dim(X) d = dim ( X ) , and let ≡ \equiv ≡ be an equivariant equivalence relation on X X X decidable in time C C C . Then, one can compute the strong approximation P P P of X / ≡ X/\equiv X / ≡ together with a lift h : X ↠ P h: X \twoheadrightarrow P h : X ↠ P of the quotient map q : X → X / ≡ q: X \to X/\equiv q : X → X / ≡ , i.e., an equivariant surjection satisfying p ∘ h = q p \circ h = q p ∘ h = q for the surjection p : P ↠ X / ≡ p: P \twoheadrightarrow X/\equiv p : P ↠ X / ≡ of the strong approximation. This computation runs in time
O ( N ( X ) 2 ⋅ β ( d , d ) ⋅ ( C + μ ( d ) ) ) , O\left(N(X)^2 \cdot\beta(d,d) \cdot(C+\mu(d))\right), O ( N ( X ) 2 ⋅ β ( d , d ) ⋅ ( C + μ ( d )) ) , polynomial in N ( X ) N(X) N ( X ) but, since β ( d , d ) = O ( 2 d d ! ) \beta(d,d) = O(2^{d}d!) β ( d , d ) = O ( 2 d d !) , factorial in d d d .
The factorial cost is inherent to this construction, as the algorithm must enumerate all β ( d , d ) \beta(d,d) β ( d , d ) partial bijections per orbit pair. By Lemma 5.2, minimization (Moore’s algorithm [26 ] ) and learning (ν L ∗ \nu L^* ν L ∗ [24 ] ) yield the following bounds (pseudocode and proofs in Appendix § 16 ).
Theorem 5.3 (minimization). Let A \mathcal{A} A be a reachable strong nominal automaton over a strong alphabet Σ \Sigma Σ , with N ( Q ) N(Q) N ( Q ) state orbits, d = dim ( Q ) d = \dim(Q) d = dim ( Q ) , and e = dim ( Σ ) e = \dim(\Sigma) e = dim ( Σ ) . Moore’s algorithm computes a strong lift of the minimal automaton of L ( A ) L(\mathcal{A}) L ( A ) in time
O ( N ( Q ) 3 ⋅ d ⋅ β ( d , d ) ⋅ N ( Σ ) β ( 2 d , e ) ⋅ μ ( d ) ) , O\left(N(Q)^3 \cdot d \cdot\beta(d,d) \cdot N(\Sigma)\beta(2d,e) \cdot\mu(d)\right), O ( N ( Q ) 3 ⋅ d ⋅ β ( d , d ) ⋅ N ( Σ ) β ( 2 d , e ) ⋅ μ ( d ) ) , which, for a fixed e e e , is polynomial in N ( Q ) N(Q) N ( Q ) and N ( Σ ) N(\Sigma) N ( Σ ) but factorial in d d d .
Theorem 5.4 (learning). Let A min \mathcal{A}_{\min} A m i n be the minimal nominal automaton of an equivariant language, with n n n state orbits, state dimension d d d , and strong alphabet Σ \Sigma Σ of dimension e = dim ( Σ ) e = \dim(\Sigma) e = dim ( Σ ) ; let m m m be the length of the longest counterexample and ℓ \ell ℓ the maximum column length of the observation table (the proof shows ℓ = m + O ( n d ) \ell= m + O(nd) ℓ = m + O ( n d ) ). Then, ν L ∗ \nu L^* ν L ∗ learns a strong lift of A min \mathcal{A}_{\min} A m i n using O ( n d ) O(nd) O ( n d ) equivalence queries and
O ( n 2 d ⋅ ( m + 1 ) ⋅ N ( Σ ) ⋅ β ( e n , e ) ⋅ β ( e n , e ℓ ) ) O\left(n^2d \cdot(m+1) \cdot N(\Sigma) \cdot\beta(en,e) \cdot\beta(en,e\ell)\right) O ( n 2 d ⋅ ( m + 1 ) ⋅ N ( Σ ) ⋅ β ( e n , e ) ⋅ β ( e n , e ℓ ) ) membership queries. Each hypothesis is constructed by Lemma 5.2 in time factorial in the observation dimensions, at most e n en e n (rows) and e ℓ e\ell e ℓ (columns).
The equivalence-query count is polynomial in all parameters; the table has polynomially many cells for a fixed alphabet dimension [24 ] , but filling each cell costs one membership query per product orbit of Proposition 3.5 , whose number is factorial in e n en e n and e ℓ e\ell e ℓ .
Implementation and Experiments
We evaluate the algorithms of § 5 via our library Namae. We address two questions:
(Q1) Language equivalence (Theorem 5.1): does the algorithm remain polynomial in practice, and does Namae outperform SMT-based tools such as Nλ \lambda λ ?
(Q2) Minimization and learning (Theorems 5.3 and 5.4): do the algorithms show the expected factorial scaling in practice, and does Namae outperform existing tools?
All experiments were run on Apple M1 Pro (8 cores, 32 GB) under macOS 26.5 with Java SE 25.0.3, Scala 3.8.4, GHC 9.4.8, Apple clang 21.0.0, and Z3 4.16.0; Namae used -Xmx16G with 50 JIT warm-up iterations on fixed small instances where timed in-process, and each benchmark was run 3 times, with the median time reported and a 10-minute timeout.3
Implementation
Namae is a Scala (JVM) library that implements the three algorithms of § 5 using the array representation of § 3.2 : for language equivalence, the generating-system bisimulation search of § 5.1 , backed by a Schreier–Sims implementation; for minimization and learning, Moore’s algorithm and ν L ∗ \nu L^* ν L ∗ of § 5.2 . The latter two rely on the quotient operation of Lemma 5.2: minimization uses it to reduce the state space, and learning to construct each hypothesis. Although this paper focuses on Eq, Namae also implements Ord [40 ] within the same codebase; its supplementary Ord benchmarks are available in Appendix § 17 .§ 4 .
Language Equivalence
We evaluate the equivalence-check algorithm of Theorem 5.1 along two axes: (1) against the SMT-based tool N λ N\lambda N λ [18 ] to expose the computational advantage of the array representation, and (2) against DEQ [29 ] to quantify the overhead of generalizing from register automata to strong nominal automata. We follow DEQ’s benchmark suite [29 ] : stacks (a stack of capacity n n n ) for n = 10 , 20 , … , 500 n=10,20,\ldots,500 n = 10 , 20 , … , 500 , and CPT (“partial permutations represented compactly” [29 ] , stressing bisimulations with many partial permutations) for n = 10 , 20 , … , 100 n=10,20,\ldots,100 n = 10 , 20 , … , 100 . For the comparison against N λ N\lambda N λ , which degrades rapidly, we additionally use small stacks n = 1 , 2 , … , 15 n=1,2,\ldots,15 n = 1 , 2 , … , 15 and restrict N λ N\lambda N λ to this range, following [29 ] .
Figure 4 reports three log-log scatter plots. Panel (a) contrasts Namae with N λ N\lambda N λ on stacks: Namae takes 0.013 s at n = 15 n=15 n = 15 , while N λ N\lambda N λ needs 133 s and scales steeply. Panels (b) and (c) compare Namae with DEQ: both scale polynomially on two structurally different benchmarks. Although DEQ is faster, the gap narrows to 1.8–2.5× at the largest sizes; this residual overhead likely stems from the generalization from unary data alphabets to orbit-finite strong alphabets and from runtime constants (JVM vs. native code).
This answers (Q1): Namae stays within a small constant factor of the polynomial-time DEQ, consistent with Theorem 5.1, and outperforms N λ N\lambda N λ .
Minimization and Learning
We evaluate the quotient, minimization, and learning algorithms of Lemma 5.2 and Theorems 5.3 and 5.4 along two axes: (1) against N λ N\lambda N λ (under Eq) to show the efficiency gains over symbolic constraint solving, and (2) against Ons-HS to expose the orbit-splitting penalty of using Ord. We use three benchmark languages: Res ( n ) \operatorname{Res}(n) Res ( n ) (the running example’s language with capacity n n n ), Res F I F O ( n ) \operatorname{Res}_{\mathrm{FIFO}}(n) Res FIFO ( n ) (FIFO variant; trivial local symmetry), and MRes ( m ) \operatorname{MRes}(m) MRes ( m ) (a variant of Res ( 1 ) \operatorname{Res}(1) Res ( 1 ) whose input alphabet has dimension m m m ; minimization only).
Table 2 reports representative minimization results. Namae scales significantly better than N λ N\lambda N λ under Eq, minimizing instances where N λ N\lambda N λ times out; this gap stems from computing the quotient orbit-wise on constraint-free arrays instead of by symbolic constraint solving. The outputs differ accordingly: N λ N_\lambda N λ returns the minimal nominal automaton itself, whereas Namae returns a strong lift of it, which by Corollary 4.5 attains the minimal orbit count and dimensions on the state space but not on the transition function, whose orbits may split as in Figure 3 ; trading this minimality for trivial local symmetries is exactly what enables the efficiency observed here. Under Ord, Ons-hs suffers from orbit splitting: for ResFIFO, Ord distinguishes atom orderings the language leaves unordered, splitting each Eq-orbit into up to d ! d! d ! Ord-orbits, as predicted by Remark 2.2. This penalty is a property of the symmetry, not the implementations: indeed, Namae and Ons-hs perform comparably on the Ord inputs in Appendix I.4, with the remaining differences attributable to implementation details, showing that our speedup is due to using Eq. Conversely, Ord remains the only option for genuinely order-based languages [40 ] that cannot be expressed over Eq. The MRes(m m m ) family instead isolates the effect of the alphabet dimension: as m m m grows, Namae’s time rises sharply, consistent with Theorem 5.3.
Table 2. Table 2 Minimization results. N i n N_{\mathrm{in}} N in , N m i n N_{\mathrm{min}} N min : state orbit counts before/after minimization; Δ m i n \Delta_{\mathrm{min}} Δ min : minimized transition-function size; > > > 10 min: timeout; —: unavailable. Full data: Appendix I.4.
Table 3 reports representative ν L ∗ \nu L^* ν L ∗ learning results. Namae learns these languages in seconds, while N λ N_\lambda N λ times out on larger instances. The measured membership-query counts remain modest, far below the worst-case bound of Theorem 5.4; Ons-hs suffers from the same orbit-splitting blowup as in minimization.
Table 3. Table 3 ν L ∗ \nu L^* ν L ∗ learning results. N N N : state orbit count of the target; Δ \Delta Δ : learned transition-function size; MQs: membership queries; > > > 10 min: timeout; —: unavailable. Full data: Appendix I.4.
This answers (Q2): the expected factorial scaling is indeed observed in practice, and Namae nonetheless outperforms N λ N_\lambda N λ and Ons-hs.
Related Work
Nominal-computation implementations. N λ N_\lambda N λ [18 ] and Lois [19 ] encode nominal sets as first-order formulas for SMT solvers. N λ N_\lambda N λ ’s predecessor [8 ] explored an explicit orbit representation but abandoned it: sizes are proportional to orbit counts, and its hull construction hinders extension to other symmetries such as the partial order [18 Sec. 5] ; it is, moreover, not canonical. Over Eq, our constraint-free arrays accept the orbit-count cost and provide a canonical representation of each orbit. Our experiments show that Namae’s array representation outperforms N λ \mathrm{N}\lambda N λ and scales to minimization and learning instances where N λ \mathrm{N}\lambda N λ times out. However, the SMT-based approach natively handles non-trivial local symmetries without approximations, suggesting the two paradigms could be integrated complementarily. For Ord, Ons and Ons-hs [40 ] implement the sorted array representation. Because Ord admits only trivial local symmetries, their underlying data model coincides with the Ord-variant of our theory. Namae handles both Eq and Ord within a unified codebase; extending it to other Fraïssé symmetries [8 ] , such as the timed symmetry [10 , 32 ] , is an interesting future direction.
Register automata. As § 3.2 shows, register-automaton configurations form strong nominal sets, which lets the generating system of DEQ [28 ] generalize to strong nominal automata in § 5 . Recently, Balachander et al. introduced pDRA [3 ] , a register automaton model with transition permutations. Over a single-atom alphabet, their injective register assignments and transition permutations mirror our array representation for states and equivariant maps. While they observed that pDRAs correspond to nominal automata with straight state sets [3 Rem. 6] , we identify the structure behind their observations as the projective cover: their minimal pDRA matches a strong lift of Corollary 4.5, and their register-permutation isomorphism [3 Rem. 20] reflects the freedom of projective-cover lifts discussed in § 4.2 . Generalizing the memorable-query minimization of Benedikt et al. [4 ] , they also proposed Π \Pi Π -DRA [3 ] , which fixes a global permutation policy Π \Pi Π at the cost of a factorial blow-up in states and admits polynomial-time active learning using memorable queries [3 Thm. 34] . Since their memorability query (mem L ( u ) = supp ( u − 1 L ) \operatorname{mem}_{L}(u) = \operatorname{supp}(u^{-1}L) mem L ( u ) = supp ( u − 1 L ) ) is simply a support query in nominal terms, this offers a promising foundation for learning strong nominal automata. Tree-based register-automaton learning (SL⋆ ^{\star} ⋆ [11 ] and SLλ ^{\lambda} λ [13 ] ) is another natural target for strong nominal adaptation.
Other adjunctions. Beyond the adjunction F ⊣ U : N o m ⇄ [ ∣ I ∣ , S e t ] F \dashv U : \mathrm{Nom} \rightleftarrows[\lvert I\rvert, \mathrm{Set}] F ⊣ U : Nom ⇄ [∣ I ∣ , Set ] underlying our theory in § 3 , two other categorical frameworks offer relevant perspectives. First, Wißmann [41 ] proves that N o m S \mathrm{Nom}_{S} Nom S is monadic over supported sets Supp ( A ) \operatorname{Supp}(A) Supp ( A ) for various symmetries. This monadicity provides an alternative algebraic foundation where a register automaton is a finite supported coalgebra whose generalized powerset yields the nominal configuration automaton, structurally complementing our view of strong nominal sets as register-automaton configurations. Second, Moerman and Rot [23 ] define an adjunction between nominal sets with substitution and standard nominal sets (i.e., N o m E q \mathrm{Nom}_{\mathrm{Eq}} Nom Eq ). Its left adjoint maps the separated product X ∗ Y X * Y X ∗ Y (pairs with disjoint supports) to the Cartesian product. This leads to separated nominal automata with restricted transition domains Q ∗ Σ Q * \Sigma Q ∗ Σ , which can be exponentially more concise for substitution-closed languages. As support disjointness is efficiently computable in our array representation, integrating the separated product is a promising extension.
Conclusion
This paper recasts strong nominal sets , for which canonical minimization is known to fail, as an efficient foundation for nominal computation. Specifically, through Theorem 3.4 , the absence of local symmetries enables the constraint-free array representation , and Theorems 4.2 and 4.3 ensure that projective covers provide strong approximations of nominal sets preserving orbit count and dimensions. This shift in perspective bridges the algorithmic gap for equivalence, which Theorem 5.1 decides in polynomial time for a fixed alphabet dimension, and extends the orbit-wise approach to minimization and learning in Theorems 5.3 and 5.4.
In experiments, Namae outperforms existing nominal-computation tools and, at scale, stays within a small constant factor of the dedicated register-automaton tool DEQ.
Several promising directions remain. Extending the categorical characterization beyond the equality symmetry to other Fraïssé symmetries, such as the timed symmetry [10 , 32 ] , is a natural next step. Furthermore, integrating concepts such as memorable queries [3 ] and separated products [23 ] into strong nominal sets could yield further algorithmic improvements.
Proof of the Local-Symmetry Characterization
This appendix proves the local-symmetry characterization of § 3 ; as there, S S S is an arbitrary data symmetry admitting least supports.
Proposition 3.3 (local-symmetry characterization). A nominal set X X X is strong if and only if every element x ∈ X x \in X x ∈ X has trivial local symmetry, i.e., Stab G ( x ) ∣ supp ( x ) = { id } \operatorname{Stab}_G(x)|_{\operatorname{supp}(x)} = \{\operatorname{id}\} Stab G ( x ) ∣ supp ( x ) = { id } .
Proof. The statement follows by unfolding the definitions:
X is a strong nominal set ⟺ ∀ x ∈ X . supp ( x ) strongly supports x (def. of strong nominal set) ⟺ ∀ x ∈ X , g ∈ G . g ⋅ x = x ⟹ g ∈ Fix G ( supp ( x ) ) (def. of strong support) ⟺ ∀ x ∈ X , g ∈ Stab G ( x ) , a ∈ supp ( x ) . g ( a ) = a (def. of Stab, Fix) ⟺ ∀ x ∈ X . Stab G ( x ) ∣ supp ( x ) = { id } (def. of local symmetry). \begin{aligned}
X\text{ is a strong nominal set}
&\Longleftrightarrow\forall x \in X.\ \operatorname{supp}(x)\text{ strongly supports }x &&\text{(def. of strong nominal set)}\\
&\Longleftrightarrow\forall x \in X,\, g \in G.\ g \cdot x=x \Longrightarrow g \in\operatorname{Fix}_{G}(\operatorname{supp}(x)) &&\text{(def. of strong support)}\\
&\Longleftrightarrow\forall x \in X,\, g \in\operatorname{Stab}_{G}(x),\, a \in\operatorname{supp}(x).\ g(a)=a &&\text{(def. of Stab, Fix)}\\
&\Longleftrightarrow\forall x \in X.\ \operatorname{Stab}_{G}(x)|_{\operatorname{supp}(x)}=\{\operatorname{id}\} &&\text{(def. of local symmetry).}
\end{aligned} X is a strong nominal set ⟺ ∀ x ∈ X . supp ( x ) strongly supports x ⟺ ∀ x ∈ X , g ∈ G . g ⋅ x = x ⟹ g ∈ Fix G ( supp ( x )) ⟺ ∀ x ∈ X , g ∈ Stab G ( x ) , a ∈ supp ( x ) . g ( a ) = a ⟺ ∀ x ∈ X . Stab G ( x ) ∣ supp ( x ) = { id } (def. of strong nominal set) (def. of strong support) (def. of Stab, Fix) (def. of local symmetry).
Proofs for Section 3.1
This appendix proves Theorem 3.4 by establishing its four equivalences separately, as Lemmas B.1, B.3, B.5, and B.6. Throughout, S = E q S=\mathrm{Eq} S = Eq and we drop it from the notation; unlike Appendix A, which works over any data symmetry admitting least supports, the equality symmetry is essential here, as the swap arguments below use arbitrary transpositions.
The Kleisli Characterization
Lemma B.1 (SNom ≃ Kl ( T ) \simeq\operatorname{Kl}(T) ≃ Kl ( T ) ). The comparison functor K : Kl ( T ) → Nom K:\operatorname{Kl}(T)\to\operatorname{Nom} K : Kl ( T ) → Nom , K ( Y ) = F ( Y ) K(Y)=F(Y) K ( Y ) = F ( Y ) , restricts to an equivalence Kl ( T ) ≃ S N o m \operatorname{Kl}(T)\simeq\mathbf{SNom} Kl ( T ) ≃ SNom .
Proof. For any adjunction F ⊣ U F\dashv U F ⊣ U , the Kleisli category is equivalent to the full subcategory of free algebras, and K K K is the induced inclusion into Nom \operatorname{Nom} Nom ; hence K K K is fully faithful and its essential image is the image of F F F . By [33 Lem. 2.4.2] , X ∈ Nom X\in\operatorname{Nom} X ∈ Nom is strong iff X ≅ F ( Y ) X\cong F(Y) X ≅ F ( Y ) for some Y ∈ [ ∣ I ∣ , Set ] Y\in[|I|,\operatorname{Set}] Y ∈ [ ∣ I ∣ , Set ] , so the essential image of K K K is exactly S N o m \mathbf{SNom} SNom . Therefore K K K restricts to an equivalence Kl ( T ) ≃ S N o m \operatorname{Kl}(T)\simeq\mathbf{SNom} Kl ( T ) ≃ SNom .
The fact that F F F lands in the strong nominal sets was already observed in [20 Footnote 1] ; Lemma B.1 records the resulting equivalence and identifies S N o m \mathbf{SNom} SNom with the free part of Nom \operatorname{Nom} Nom . Our formula F ( Y ) = ∐ C Y ( C ) × Inj ( C , N ) F(Y)=\coprod_{C}Y(C)\times\operatorname{Inj}(C,\mathbb{N}) F ( Y ) = ∐ C Y ( C ) × Inj ( C , N ) from § 3.1 is the tuple presentation of the left adjoint of [20 , 33 ] , to which it is naturally isomorphic.
The Free-Coproduct-Completion Characterization
Lemma B.2 (S N o m 1 ≃ I o p \mathbf{SNom}^{1}\simeq I^{\mathrm{op}} SNom 1 ≃ I op ). The functor Φ : I o p → S N o m 1 \Phi:I^{\mathrm{op}}\to\mathbf{SNom}^{1} Φ : I op → SNom 1 defined by Φ ( C ) = Inj ( C , N ) \Phi(C)=\operatorname{Inj}(C,\mathbb{N}) Φ ( C ) = Inj ( C , N ) and Φ ( h ) ( e ) = e ∘ h \Phi(h)(e)=e\circ h Φ ( h ) ( e ) = e ∘ h for an injection h : D ↪ C h:D\hookrightarrow C h : D ↪ C in I I I is an equivalence of categories.
Proof. First, Φ \Phi Φ is well defined: each Inj ( C , N ) \operatorname{Inj}(C,\mathbb{N}) Inj ( C , N ) is a transitive G G G -set and is strong, since g ⋅ e = g ∘ e = e g\cdot e=g\circ e=e g ⋅ e = g ∘ e = e forces g g g to fix e ( C ) = supp ( e ) e(C)=\operatorname{supp}(e) e ( C ) = supp ( e ) pointwise, and Φ ( h ) \Phi(h) Φ ( h ) is equivariant. It remains to show Φ \Phi Φ is fully faithful and essentially surjective.
Fully faithful. Let f : Inj ( C , N ) → Inj ( D , N ) f:\operatorname{Inj}(C,\mathbb{N})\to\operatorname{Inj}(D,\mathbb{N}) f : Inj ( C , N ) → Inj ( D , N ) be equivariant; fix e 0 e_{0} e 0 and put e 0 ′ = f ( e 0 ) e'_{0}=f(e_{0}) e 0 ′ = f ( e 0 ) . By transitivity, every e e e has the form g ∘ e 0 g\circ e_{0} g ∘ e 0 , so f ( e ) = g ∘ e 0 ′ f(e)=g\circ e'_{0} f ( e ) = g ∘ e 0 ′ and f f f is determined by e 0 ′ e'_{0} e 0 ′ . If some d d d had e ′ ( d ) = a e'(d)=a e ′ ( d ) = a and a ∉ e 0 ( C ) a\notin e_{0}(C) a ∈ / e 0 ( C ) , choose b ∉ e 0 ( C ) ∪ e ′ ( D ) b\notin e_{0}(C)\cup e'(D) b ∈ / e 0 ( C ) ∪ e ′ ( D ) ; then ( a b ) ∘ e 0 = e 0 (a\ b)\circ e_{0}=e_{0} ( a b ) ∘ e 0 = e 0 while ( a b ) ∘ e 0 ′ ≠ e 0 ′ (a\ b)\circ e'_{0}\ne e'_{0} ( a b ) ∘ e 0 ′ = e 0 ′ , contradicting equivariance. Hence e ′ ( D ) ⊆ e 0 ( C ) e'(D)\subseteq e_{0}(C) e ′ ( D ) ⊆ e 0 ( C ) , and h = e 0 − 1 ∘ e ′ : D ↪ C h=e_{0}^{-1}\circ e':D\hookrightarrow C h = e 0 − 1 ∘ e ′ : D ↪ C satisfies f = Φ ( h ) f=\Phi(h) f = Φ ( h ) ; injectivity of e 0 e_{0} e 0 makes h h h unique.
Essentially surjective. For X ∈ S N o m 1 X\in\mathbf{SNom}^{1} X ∈ SNom 1 pick x 0 x_{0} x 0 with C = supp ( x 0 ) C=\operatorname{supp}(x_{0}) C = supp ( x 0 ) and let e 0 : C ↪ N e_{0}:C\hookrightarrow\mathbb{N} e 0 : C ↪ N be the inclusion. Strongness gives Stab G ( x 0 ) = Fix G ( C ) = Stab G ( e 0 ) \operatorname{Stab}_{G}(x_{0})=\operatorname{Fix}_{G}(C)=\operatorname{Stab}_{G}(e_{0}) Stab G ( x 0 ) = Fix G ( C ) = Stab G ( e 0 ) , so by the orbit–stabilizer theorem X ≅ G / Fix G ( C ) ≅ Inj ( C , N ) = Φ ( C ) X\cong G/\operatorname{Fix}_{G}(C)\cong\operatorname{Inj}(C,\mathbb{N})=\Phi(C) X ≅ G / Fix G ( C ) ≅ Inj ( C , N ) = Φ ( C ) .
Lemma B.3 (S N o m ≃ Fam ( I o p ) \mathbf{SNom}\simeq\operatorname{Fam}(I^{\mathrm{op}}) SNom ≃ Fam ( I op ) ). S N o m \mathbf{SNom} SNom is equivalent to the free coproduct completion Fam ( I o p ) \operatorname{Fam}(I^{\mathrm{op}}) Fam ( I op ) .
Proof. Every strong nominal set is the coproduct of its orbits, and by transitivity of the G G G -action, every equivariant map from a single orbit into a coproduct factors through a unique summand. Hence SNom is the free coproduct completion of its full subcategory SNom 1 ^{1} 1 of single orbits, and Lemma B.2 gives S N o m ≃ Fam ( S N o m 1 ) ≃ Fam ( I o p ) \mathbf{SNom} \simeq\operatorname{Fam}(\mathbf{SNom}^{1}) \simeq\operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) SNom ≃ Fam ( SNom 1 ) ≃ Fam ( I op ) .
Under Φ \Phi Φ , a single orbit corresponds to a finite set C C C , hence to its dimension ∣ C ∣ |C| ∣ C ∣ , and an element to an injection C ↪ N C \hookrightarrow\mathbb{N} C ↪ N , i.e., a tuple of ∣ C ∣ |C| ∣ C ∣ distinct atoms. This is the source of the array representation of Section 3.2.
Family-style representations are classical for arbitrary orbit-finite nominal sets, with a local symmetry group attached to each orbit: the single-orbit case over Fraïssé symmetries is given in [9 Thm. 10.9] , and extended to orbit-finite families over algebraic atoms in [32 Thm. 4.19] . Lemma B.3 complements these by identifying the strong fragment as precisely a free coproduct completion .
A free-coproduct-completion presentation also appears in the named-set literature: the bijection-based category N S e t B \mathbf{NSet}_{\mathbb{B}} NSet B of named sets with symmetries arises as a free coproduct completion of the coset actions of the symmetric groups, with N S e t B ≃ [ B , S e t ] \mathbf{NSet}_{\mathbb{B}} \simeq[\mathbb{B}, \mathbf{Set}] NSet B ≃ [ B , Set ] for the groupoid B \mathbb{B} B of finite sets and bijections [36 Sec. 5.1] ; this is generalized to arbitrary small categories C C C of monos in [12 ] : pullback-preserving presheaves over C C C are equivalent to Fam ( Sym ( C ) o p ) \operatorname{Fam}(\operatorname{Sym}(C)^{\mathrm{op}}) Fam ( Sym ( C ) op ) , where Sym ( C ) \operatorname{Sym}(C) Sym ( C ) is the category of automorphism groups over C C C . Over C = I C = \mathbb{I} C = I , this equivalence gives N o m ≃ Fam ( Sym ( I ) o p ) \mathbf{Nom} \simeq\operatorname{Fam}(\operatorname{Sym}(\mathbb{I})^{\mathrm{op}}) Nom ≃ Fam ( Sym ( I ) op ) ; Lemma B.3 identifies the trivial-symmetry fragment Fam ( I o p ) \operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) Fam ( I op ) as exactly SNom .
The Projective Characterization
A section of an epimorphism e : X ↠ Y e: X \twoheadrightarrow Y e : X ↠ Y is a map s : Y → X s: Y \rightarrow X s : Y → X with e ∘ s = id Y e \circ s = \operatorname{id}_{Y} e ∘ s = id Y ; in particular, if Y Y Y is projective in the sense of Section 2, then lifting id Y \operatorname{id}_{Y} id Y along e e e shows that every epimorphism onto Y Y Y admits a section . More generally, B B B is a retract of A A A if there are i : B → A i: B \rightarrow A i : B → A and r : A → B r: A \rightarrow B r : A → B with r ∘ i = id B r \circ i = \operatorname{id}_{B} r ∘ i = id B , i.e., i i i is a section of r r r ; retracts of projective objects are again projective (lift along r r r , then compose with i i i ). A category is idempotent complete if every idempotent e : A → A e: A \rightarrow A e : A → A (i.e., e ∘ e = e e \circ e = e e ∘ e = e ) splits as e = i ∘ r e = i \circ r e = i ∘ r for some retract pair i , r i,r i , r as above.
Lemma B.4 (Fam(C \mathcal{C} C ) inherits idempotent completeness). If C \mathcal{C} C is idempotent complete, so is Fam(C \mathcal{C} C ).
Proof. An idempotent of a family ( A i ) i ∈ I ∈ Fam ( C ) (A_i)_{i\in I} \in\operatorname{Fam}(\mathcal{C}) ( A i ) i ∈ I ∈ Fam ( C ) is a morphism ( ρ , ( f i ) i ∈ I ) (\rho,(f_i)_{i\in I}) ( ρ , ( f i ) i ∈ I ) with ρ : I → I \rho: I \rightarrow I ρ : I → I and f i : A i → A ρ ( i ) f_i: A_i \rightarrow A_{\rho(i)} f i : A i → A ρ ( i ) satisfying ρ ∘ ρ = ρ \rho\circ\rho= \rho ρ ∘ ρ = ρ and f ρ ( i ) ∘ f i = f i f_{\rho(i)} \circ f_i = f_i f ρ ( i ) ∘ f i = f i for all i ∈ I i \in I i ∈ I ; in particular, every ρ ( i ) \rho(i) ρ ( i ) is a fixed point of ρ \rho ρ , and f i f_i f i is an idempotent endomorphism for each fixed point i i i . Write I ′ ⊆ I I' \subseteq I I ′ ⊆ I for the set of fixed points of ρ \rho ρ and, using the idempotent completeness of C \mathcal{C} C , split f i = m i ∘ r i f_i = m_i \circ r_i f i = m i ∘ r i through an object B i B_i B i for each i ∈ I ′ i \in I' i ∈ I ′ . Then the family ( B i ) i ∈ I ′ (B_i)_{i\in I'} ( B i ) i ∈ I ′ splits the idempotent: the morphisms ( ρ , ( r ρ ( i ) ∘ f i ) i ∈ I ) : ( A i ) i ∈ I → ( B i ) i ∈ I ′ (\rho,(r_{\rho(i)} \circ f_i)_{i\in I}): (A_i)_{i\in I} \rightarrow(B_i)_{i\in I'} ( ρ , ( r ρ ( i ) ∘ f i ) i ∈ I ) : ( A i ) i ∈ I → ( B i ) i ∈ I ′ and ( ι , ( m i ) i ∈ I ′ ) (\iota,(m_i)_{i\in I'}) ( ι , ( m i ) i ∈ I ′ ) in the opposite direction, where ι : I ′ ↪ I \iota: I' \hookrightarrow I ι : I ′ ↪ I is the inclusion, compose to id \operatorname{id} id on ( B i ) i ∈ I ′ (B_i)_{i\in I'} ( B i ) i ∈ I ′ and to ( ρ , ( f i ) i ∈ I ) (\rho,(f_i)_{i\in I}) ( ρ , ( f i ) i ∈ I ) on ( A i ) i ∈ I (A_i)_{i\in I} ( A i ) i ∈ I , using r i ∘ m i = id B i r_i \circ m_i = \operatorname{id}_{B_i} r i ∘ m i = id B i and f ρ ( i ) ∘ f i = f i f_{\rho(i)} \circ f_i = f_i f ρ ( i ) ∘ f i = f i .
The only idempotents in I \mathbb{I} I are identities, so I \mathbb{I} I (and hence I o p \mathbb{I}^{\mathrm{op}} I op ) is idempotent complete. By Lemma B.4, Fam ( I o p ) \operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) Fam ( I op ) is idempotent complete, and therefore so is SNom .
We record the action of the comparison functor J J J on morphisms, which Section 3.1 leaves implicit: for a morphism i : C → D i: C \rightarrow D i : C → D of I \mathbb{I} I and x ∈ J ( X ) ( C ) x \in J(X)(C) x ∈ J ( X ) ( C ) , we set J ( X ) ( i ) ( x ) = i ^ ⋅ x J(X)(i)(x) = \hat{i} \cdot x J ( X ) ( i ) ( x ) = i ^ ⋅ x , where i ^ ∈ G \hat{i} \in G i ^ ∈ G is any finite permutation extending i i i . This is well defined, since two extensions of i i i differ by a permutation fixing C C C pointwise, which fixes x x x as supp ( x ) ⊆ C \operatorname{supp}(x) \subseteq C supp ( x ) ⊆ C ; moreover supp ( i ^ ⋅ x ) = i ^ ( supp ( x ) ) ⊆ D \operatorname{supp}(\hat{i} \cdot x) = \hat{i}(\operatorname{supp}(x)) \subseteq D supp ( i ^ ⋅ x ) = i ^ ( supp ( x )) ⊆ D places i ^ ⋅ x \hat{i} \cdot x i ^ ⋅ x in J ( X ) ( D ) J(X)(D) J ( X ) ( D ) , and functoriality follows directly.
Lemma B.5 (S N o m ≃ Proj ( [ I , S e t ] ) \mathrm{SNom} \simeq\operatorname{Proj}([\mathbb{I}, \mathbf{Set}]) SNom ≃ Proj ([ I , Set ]) ). The restricted comparison functor J ′ = J ∘ ι : S N o m → [ I , S e t ] J' = J \circ\iota: \mathrm{SNom} \to[\mathbb{I}, \mathbf{Set}] J ′ = J ∘ ι : SNom → [ I , Set ] (where ι : S N o m ↪ N o m \iota: \mathrm{SNom} \hookrightarrow\mathrm{Nom} ι : SNom ↪ Nom is the inclusion, see Figure 2 ) is an equivalence onto the full subcategory Proj ( [ I , S e t ] ) \operatorname{Proj}([\mathbb{I}, \mathbf{Set}]) Proj ([ I , Set ]) of projective objects.
Proof. On a single orbit, J ′ ( Inj ( C , N ) ) ≅ I ( C , − ) J'(\operatorname{Inj}(C, \mathbb{N})) \cong\mathbb{I}(C, -) J ′ ( Inj ( C , N )) ≅ I ( C , − ) , the representable functor at C C C . By the Yoneda lemma representables are projective, and coproducts of projectives are projective, so the essential image of J ′ J' J ′ is contained in Proj ( [ I , S e t ] ) \operatorname{Proj}([\mathbb{I}, \mathbf{Set}]) Proj ([ I , Set ]) . Conversely, every projective object of [ I , S e t ] [\mathbb{I}, \mathbf{Set}] [ I , Set ] is a retract of a coproduct of representables, hence a retract of some J ′ ( X ) J'(X) J ′ ( X ) with X ∈ S N o m X \in\mathrm{SNom} X ∈ SNom . Since S N o m \mathrm{SNom} SNom is idempotent complete and J ′ J' J ′ is fully faithful, the essential image of J ′ J' J ′ is closed under retracts. So every such projective is isomorphic to some J ′ ( X ) J'(X) J ′ ( X ) . Thus J ′ J' J ′ is essentially surjective onto Proj ( [ I , S e t ] ) \operatorname{Proj}([\mathbb{I}, \mathbf{Set}]) Proj ([ I , Set ]) .
Projectivity here is relative to [ I , S e t ] [\mathbb{I}, \mathbf{Set}] [ I , Set ] . In Nom itself, only the empty set ∅ \varnothing ∅ is projective: for any non-empty nominal set X X X , the equivariant surjection fst : { ( x , a ) ∈ X × N ∣ a ∉ supp ( x ) } ↠ X \operatorname{fst}: \{(x,a) \in X \times\mathbb{N} \mid a \notin\operatorname{supp}(x)\} \twoheadrightarrow X fst : {( x , a ) ∈ X × N ∣ a ∈ / supp ( x )} ↠ X , defined by fst ( x , a ) = x \operatorname{fst}(x,a)=x fst ( x , a ) = x , has no equivariant section. Indeed, any section s s s of fst \operatorname{fst} fst must have the form s ( x ) = ( x , α ( x ) ) s(x)=(x,\alpha(x)) s ( x ) = ( x , α ( x )) for some function α : X → N \alpha:X \to\mathbb{N} α : X → N , and since s ( x ) s(x) s ( x ) lies in the domain of fst \operatorname{fst} fst , α ( x ) ∉ supp ( x ) \alpha(x) \notin\operatorname{supp}(x) α ( x ) ∈ / supp ( x ) for all x x x . The domain of fst \operatorname{fst} fst is orbit-finite whenever X X X is, so the failure persists among orbit-finite nominal sets. Equivariance of s s s forces α \alpha α to be equivariant as well, so supp ( α ( x ) ) ⊆ supp ( x ) \operatorname{supp}(\alpha(x)) \subseteq\operatorname{supp}(x) supp ( α ( x )) ⊆ supp ( x ) ; since α ( x ) \alpha(x) α ( x ) is itself an atom, supp ( α ( x ) ) = { α ( x ) } \operatorname{supp}(\alpha(x))=\{\alpha(x)\} supp ( α ( x )) = { α ( x )} , giving α ( x ) ∈ supp ( x ) \alpha(x) \in\operatorname{supp}(x) α ( x ) ∈ supp ( x ) , which contradicts α ( x ) ∉ supp ( x ) \alpha(x) \notin\operatorname{supp}(x) α ( x ) ∈ / supp ( x ) . Therefore, any non-empty nominal set X X X is not projective in Nom . The strong nominal sets acquire projectivity only once transported along J ′ J' J ′ into the functor category.
The Named-Set Characterization
We first recall the terminology of named sets from the theory of history-dependent automata. We follow the early definition of [25 ] , which does not yet involve permutation groups (i.e., local symmetries): a named set is a set I I I of elements equipped with a name set C i C_i C i for each i ∈ I i \in I i ∈ I , and a named function from ( C i ) i ∈ I (C_i)_{i \in I} ( C i ) i ∈ I to ( D j ) j ∈ J (D_j)_{j \in J} ( D j ) j ∈ J is a pair ( ρ , ( h i ) i ∈ I ) (\rho,(h_i)_{i \in I}) ( ρ , ( h i ) i ∈ I ) of a function ρ : I → J \rho:I \to J ρ : I → J and name embeddings , i.e., injections h i : D ρ ( i ) ↪ C i h_i:D_{\rho(i)} \hookrightarrow C_i h i : D ρ ( i ) ↪ C i . A named set is finitely named if every name set C i C_i C i is finite; without loss of generality, we take the name sets of finitely named sets to be finite subsets of N \mathbb{N} N . We write N S e t f n \mathrm{NSet}_{\mathrm{fn}} NSet fn for the category of finitely named sets and named functions.
Lemma B.6 (S N o m ≃ N S e t f n \mathrm{SNom} \simeq\mathrm{NSet}_{\mathrm{fn}} SNom ≃ NSet fn ). S N o m \mathrm{SNom} SNom is equivalent to the category N S e t f n \mathrm{NSet}_{\mathrm{fn}} NSet fn of finitely named sets.
Proof. An object of Fam ( I o p ) \operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) Fam ( I op ) is a family ( C i ) i ∈ I (C_i)_{i \in I} ( C i ) i ∈ I of finite subsets of N \mathbb{N} N , which is exactly a finitely named set, and a morphism ( ρ , ( h i ) i ∈ I ) (\rho,(h_i)_{i \in I}) ( ρ , ( h i ) i ∈ I ) of Fam ( I o p ) \operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) Fam ( I op ) is exactly a named function between finitely named sets. This identification is the identity on objects and morphisms, so Fam ( I o p ) = N S e t f n \operatorname{Fam}(\mathbb{I}^{\mathrm{op}})=\mathrm{NSet}_{\mathrm{fn}} Fam ( I op ) = NSet fn , and Lemma B.3 gives S N o m ≃ N S e t f n \mathrm{SNom} \simeq\mathrm{NSet}_{\mathrm{fn}} SNom ≃ NSet fn .
The contemporary definition of named sets [14 Sec. 3.1] [16 Defs. 22–23] additionally equips each element with a permutation group and defines named functions up to the action of these groups: a morphism assigns to each element a non-empty set of injections, saturated under the permutation groups of its source and target. This yields the category N S e t I \mathrm{NSet}_{\mathbb{I}} NSet I of named sets with permutation groups, as recalled in § 3.1 ; the notation follows [36 Sec. 5.1] , which distinguishes these injection-based morphisms from the injection-based variant N S e t B ≃ [ B , S e t ] \mathrm{NSet}_{\mathbb{B}} \simeq[\mathbb{B}, \mathbf{Set}] NSet B ≃ [ B , Set ] discussed in Appendix § 10 .§ 2 , proves N S e t I \mathrm{NSet}_{\mathbb{I}} NSet I equivalent to the Schanuel topos, and identifies it as “essentially” the category of [14 Sec. 3.1] , the differences (a total order on the elements, and possibly empty sets of injections there) being immaterial.
:::
Under N o m ≃ N S e t I \mathbf{Nom} \simeq\mathbf{NSet}_{\mathbb{I}} Nom ≃ NSet I , strong nominal sets correspond, by Proposition 3.3, to those named sets whose permutation groups are all trivial; the saturation condition then collapses each set of injections to a singleton, so between such objects the morphisms of N S e t I \mathbf{NSet}_{\mathbb{I}} NSet I are exactly the named functions of Lemma B.6. This full subcategory is precisely N S e t f n \mathbf{NSet}_{\mathrm{fn}} NSet fn , formally linking strong nominal sets to the original formulation of history-dependent automata.
Finally, assembling these four categorical equivalences completes the full picture of strong nominal sets.
Proof of Theorem 3.4. Lemmas B.1, B.3, B.5, and B.6 together establish the theorem.
Proofs for Counting Product Orbits
We prove Proposition 3.5 by separating its three claims: each partial bijection determines one orbit per Lemma C.1, these orbits exhaust the product according to Lemma C.2, and the partial bijections are counted by the stated sum as verified in Lemma C.3.
By the array representation, an element of X × Y X \times Y X × Y is a pair ( a ⃗ , b ⃗ ) (\vec{a},\vec{b}) ( a , b ) of tuples a ⃗ = ⟨ a 1 , … , a m ⟩ \vec{a} = \langle a_1,\ldots,a_m\rangle a = ⟨ a 1 , … , a m ⟩ and b ⃗ = ⟨ b 1 , … , b n ⟩ \vec{b} = \langle b_1,\ldots,b_n\rangle b = ⟨ b 1 , … , b n ⟩ , each consisting of pairwise distinct atoms. Its coincidence pattern is the relation π ( a ⃗ , b ⃗ ) ⊆ [ m ] × [ n ] \pi_{(\vec{a},\vec{b})} \subseteq[m] \times[n] π ( a , b ) ⊆ [ m ] × [ n ] defined by π ( a ⃗ , b ⃗ ) ( i ) = j \pi_{(\vec{a},\vec{b})}(i) = j π ( a , b ) ( i ) = j iff a i = b j a_i = b_j a i = b j . Since the a i a_i a i are pairwise distinct and so are the b j b_j b j , each index i i i corresponds to at most one index j j j , and vice versa, so π ( a ⃗ , b ⃗ ) \pi_{(\vec{a},\vec{b})} π ( a , b ) is a partial bijection [ m ] ⇀ [ n ] [m] \rightharpoonup[n] [ m ] ⇀ [ n ] . For a partial bijection π : [ m ] ⇀ [ n ] \pi: [m] \rightharpoonup[n] π : [ m ] ⇀ [ n ] , we write
⟦ π ⟧ = { ( a ⃗ , b ⃗ ) ∈ X × Y ∣ π ( a ⃗ , b ⃗ ) = π } \llbracket\pi\rrbracket= \{(\vec{a},\vec{b}) \in X \times Y \mid\pi_{(\vec{a},\vec{b})} = \pi\} [ [ π ] ] = {( a , b ) ∈ X × Y ∣ π ( a , b ) = π }
for the set of pairs realizing exactly the coincidence pattern π \pi π .
Lemma C.1 (partial bijections determine orbits). For every partial bijection π : [ m ] ⇀ [ n ] \pi: [m] \rightharpoonup[n] π : [ m ] ⇀ [ n ] , the set ⟦ π ⟧ \llbracket\pi\rrbracket [ [ π ] ] is a single strong orbit of X × Y X \times Y X × Y of dimension m + n − ∣ dom ( π ) ∣ m+n-|\operatorname{dom}(\pi)| m + n − ∣ dom ( π ) ∣ .
Proof. First, ⟦ π ⟧ \llbracket\pi\rrbracket [ [ π ] ] is equivariant: every g ∈ G g \in G g ∈ G acts by relabeling atoms and hence preserves coincidences, so π g ⋅ ( a ⃗ , b ⃗ ) = π ( a ⃗ , b ⃗ ) \pi_{g\cdot(\vec{a},\vec{b})} = \pi_{(\vec{a},\vec{b})} π g ⋅ ( a , b ) = π ( a , b ) , whence g ⋅ ⟦ π ⟧ = ⟦ π ⟧ g \cdot\llbracket\pi\rrbracket= \llbracket\pi\rrbracket g ⋅ [ [ π ] ] = [ [ π ] ] . It is nonempty, as π \pi π is realized by choosing atoms that coincide exactly as π \pi π prescribes (which is always possible since the supply of atoms is infinite). It is a single orbit: given ( a ⃗ , b ⃗ ) , ( a ⃗ ′ , b ⃗ ′ ) ∈ ⟦ π ⟧ (\vec{a},\vec{b}),(\vec{a}',\vec{b}') \in\llbracket\pi\rrbracket ( a , b ) , ( a ′ , b ′ ) ∈ [ [ π ] ] , the map sending each atom of ( a ⃗ , b ⃗ ) (\vec{a},\vec{b}) ( a , b ) to the atom in the corresponding position of ( a ⃗ ′ , b ⃗ ′ ) (\vec{a}',\vec{b}') ( a ′ , b ′ ) is well defined and injective precisely because both share the coincidence pattern π \pi π ; since G = Sym ( N ) G = \operatorname{Sym}(\mathbb{N}) G = Sym ( N ) , as a finite partial injection of N \mathbb{N} N it extends to some g ∈ G g \in G g ∈ G with g ⋅ ( a ⃗ , b ⃗ ) = ( a ⃗ ′ , b ⃗ ′ ) g \cdot(\vec{a},\vec{b}) = (\vec{a}',\vec{b}') g ⋅ ( a , b ) = ( a ′ , b ′ ) . The least support of ( a ⃗ , b ⃗ ) (\vec{a},\vec{b}) ( a , b ) is the set of atoms occurring in the pair; the two tuples contribute m + n m+n m + n atoms with exactly ∣ dom ( π ) ∣ |\operatorname{dom}(\pi)| ∣ dom ( π ) ∣ coincidences identified, so dim ( ⟦ π ⟧ ) = m + n − ∣ dom ( π ) ∣ \dim(\llbracket\pi\rrbracket) = m+n-|\operatorname{dom}(\pi)| dim ( [ [ π ] ] ) = m + n − ∣ dom ( π ) ∣ . Finally, ⟦ π ⟧ \llbracket\pi\rrbracket [ [ π ] ] is strong: if g ⋅ ( a ⃗ , b ⃗ ) = ( a ⃗ , b ⃗ ) g \cdot(\vec{a},\vec{b}) = (\vec{a},\vec{b}) g ⋅ ( a , b ) = ( a , b ) , then g g g fixes every atom occurring in the pair, hence all of supp ( a ⃗ , b ⃗ ) \operatorname{supp}(\vec{a},\vec{b}) supp ( a , b ) .
Lemma C.2 (the orbits exhaust the product). X × Y = ∐ π ⟦ π ⟧ X \times Y = \coprod_{\pi} \llbracket\pi\rrbracket X × Y = ∐ π [ [ π ] ] , where π \pi π ranges over all partial bijections [ m ] ⇀ [ n ] [m] \rightharpoonup[n] [ m ] ⇀ [ n ] .
Proof. Each pair ( a ⃗ , b ⃗ ) ∈ X × Y (\vec{a},\vec{b}) \in X \times Y ( a , b ) ∈ X × Y has a unique coincidence pattern π ( a ⃗ , b ⃗ ) \pi_{(\vec{a},\vec{b})} π ( a , b ) , which is a partial bijection, so it belongs to exactly one ⟦ π ⟧ \llbracket\pi\rrbracket [ [ π ] ] . Thus the sets ⟦ π ⟧ \llbracket\pi\rrbracket [ [ π ] ] are pairwise disjoint and cover X × Y X \times Y X × Y .
Lemma C.3 (number of partial bijections). The number of partial bijections [ m ] ⇀ [ n ] [m] \rightharpoonup[n] [ m ] ⇀ [ n ] is
∑ k = 0 min ( m , n ) ( m k ) ( n k ) k ! (1) \sum_{k=0}^{\min(m,n)} \binom{m}{k}\binom{n}{k}k! \tag*{(1)} k = 0 ∑ m i n ( m , n ) ( k m ) ( k n ) k ! (1)
Proof. A partial bijection with domain of size k k k is determined by a k k k -subset of [ m ] [m] [ m ] , a k k k -subset of [ n ] [n] [ n ] , and a bijection between them, giving ( m k ) ( n k ) k ! \binom{m}{k}\binom{n}{k}k! ( k m ) ( k n ) k ! choices. Summing over the possible sizes 0 ≤ k ≤ min ( m , n ) 0 \leq k \leq\min(m,n) 0 ≤ k ≤ min ( m , n ) gives the claim.
Proof of Proposition 3.5. By Lemmas C.1 and C.2, the orbits of X × Y X \times Y X × Y are exactly the sets ⟦ π ⟧ \llbracket\pi\rrbracket [ [ π ] ] for partial bijections π : [ m ] ⇀ [ n ] \pi:[m]\rightharpoonup[n] π : [ m ] ⇀ [ n ] , with dim ( ⟦ π ⟧ ) = m + n − ∣ dom ( π ) ∣ \dim(\llbracket\pi\rrbracket)=m+n-\lvert\operatorname{dom}(\pi)\rvert dim ( [ [ π ] ] ) = m + n − ∣ dom ( π )∣ . Their number is counted by Lemma C.3.
The decomposition into the orbits ⟦ π ⟧ \llbracket\pi\rrbracket [ [ π ] ] specializes the product representation of [9 Sec. 10.3] , which describes products of single orbits over general Fraïssé symmetries as coproducts indexed by partial isomorphisms between the underlying structures; over Eq with strong orbits, these partial isomorphisms are exactly the partial bijections [ m ] ⇀ [ n ] [m]\rightharpoonup[n] [ m ] ⇀ [ n ] , and the absence of local symmetries enables the explicit count of Proposition 3.5. At the family level, the same decomposition instantiates the product in Fam ( C o p ) \operatorname{Fam}(\mathcal{C}^{\mathrm{op}}) Fam ( C op ) constructed via multi-coproducts of interfaces [12 Sec. 5] : over C = I \mathcal{C}=\mathbb{I} C = I , the canonical cospans between [ m ] [m] [ m ] and [ n ] [n] [ n ] correspond precisely to the partial bijections π \pi π . The product decomposition over Ord [40 Sec. 5.3] plays the same role for sorted arrays.
D Proofs for Projective Covers as Strong Approximation
Throughout, S = E q \mathcal{S}=\mathrm{Eq} S = Eq and we drop it from the notation. Recall from Lemma B.5 that ( I ′ ( Inj ( [ n ] , N ) ) ) ≅ I ( [ n ] , − ) (\mathbb{I}'(\operatorname{Inj}([n],\mathbb{N})))\cong\mathbb{I}([n],-) ( I ′ ( Inj ([ n ] , N ))) ≅ I ([ n ] , − ) , the representable functor at [ n ] [n] [ n ] , and the action of J J J on morphisms of I \mathbb{I} I recorded in Appendix § 10 .§ 3 . Both proofs rest on the explicit projective cover built from the following notion.
Definition D.1 (new elements). For F ∈ [ I , S e t ] \mathcal{F}\in[\mathbb{I},\mathrm{Set}] F ∈ [ I , Set ] and n ≥ 0 n\geq0 n ≥ 0 , the set of new elements at level n n n is
New n ( F ) = F ( [ n ] ) ∖ ⋃ i : [ m ] ↪ [ n ] m < n F ( i ) ( F ( [ m ] ) ) , \operatorname{New}_{n}(\mathcal{F})=\mathcal{F}([n])\setminus\bigcup_{\substack{i:[m]\hookrightarrow[n]\\m<n}}\mathcal{F}(i)(\mathcal{F}([m])), New n ( F ) = F ([ n ]) ∖ i : [ m ] ↪ [ n ] m < n ⋃ F ( i ) ( F ([ m ])) , the elements of F ( [ n ] ) \mathcal{F}([n]) F ([ n ]) not in the image of any strictly smaller level.
Since each σ ∈ S n \sigma\in S_n σ ∈ S n is a bijection of [ n ] [n] [ n ] , hence a morphism of I \mathbb{I} I , the group S n S_n S n acts on F ( [ n ] ) \mathcal{F}([n]) F ([ n ]) via F ( σ ) \mathcal{F}(\sigma) F ( σ ) ; this action preserves New n ( F ) \operatorname{New}_{n}(\mathcal{F}) New n ( F ) , which therefore decomposes into a set Λ n \Lambda_n Λ n of S n S_n S n -orbits.
To prove Theorem 4.2, we build the projective cover explicitly from the new elements of Definition D.1, taking one representable summand I ( [ n ] , − ) \mathbb{I}([n],-) I ([ n ] , − ) per S n S_n S n -orbit λ ∈ Λ n \lambda\in\Lambda_n λ ∈ Λ n , and then directly verify the two defining properties of a projective cover, namely being a superfluous epimorphism. Superfluousness rests on the following lemma.
Lemma D.2 (subfunctor lemma). A proper subfunctor Z ⊊ I ( C , − ) Z\subsetneq\mathbb{I}(C,-) Z ⊊ I ( C , − ) satisfies Z ( C ) = ∅ Z(C)=\varnothing Z ( C ) = ∅ .
Proof. Suppose f ∈ Z ( C ) f\in Z(C) f ∈ Z ( C ) . As an injection of a finite set, f f f is a bijection. For any injection g : C ↪ D g:C\hookrightarrow D g : C ↪ D , the map u = g ∘ f − 1 u=g\circ f^{-1} u = g ∘ f − 1 is injective and satisfies u ∘ f = g u\circ f=g u ∘ f = g ; applying Z ( u ) Z(u) Z ( u ) to f f f therefore yields Z ( u ) ( f ) = u ∘ f = g Z(u)(f)=u\circ f=g Z ( u ) ( f ) = u ∘ f = g , so g g g belongs to Z ( D ) Z(D) Z ( D ) . Since g g g was an arbitrary injection, Z ( D ) = I ( C , D ) Z(D)=\mathbb{I}(C,D) Z ( D ) = I ( C , D ) for all D D D , contradicting properness.
Theorem 4.2 (projective cover existence). Every object F ∈ [ I , S e t ] \mathcal{F}\in[\mathbb{I},\mathrm{Set}] F ∈ [ I , Set ] admits a projective cover ( I ′ ( X ′ ) , e ) (\mathbb{I}'(X'),e) ( I ′ ( X ′ ) , e ) with a strong nominal set X ′ X' X ′ and a superfluous epimorphism e : I ′ ( X ′ ) ↠ F e:\mathbb{I}'(X')\twoheadrightarrow\mathcal{F} e : I ′ ( X ′ ) ↠ F .
Proof. For each λ ∈ Λ n \lambda\in\Lambda_n λ ∈ Λ n choose a representative x λ ∈ λ x_\lambda\in\lambda x λ ∈ λ ; by the Yoneda lemma it corresponds to a natural transformation y λ : I ( [ n ] , − ) → F y_\lambda: \mathbb{I}([n], -) \to\mathcal{F} y λ : I ([ n ] , − ) → F . Set
X ′ = ∐ n ≥ 0 , λ ∈ Λ n Inj ( [ n ] , N ) , e = ∐ n , λ y λ : J ′ ( X ′ ) → F , X' = \coprod_{\substack{n \ge0,\ \lambda\in\Lambda_n}} \operatorname{Inj}([n],\mathbb{N}), \qquad e = \coprod_{n,\lambda} y_\lambda: \mathcal{J}'(X') \to\mathcal{F}, X ′ = n ≥ 0 , λ ∈ Λ n ∐ Inj ([ n ] , N ) , e = n , λ ∐ y λ : J ′ ( X ′ ) → F ,
so that J ′ ( X ′ ) = ∐ n , λ I ( [ n ] , − ) \mathcal{J}'(X') = \coprod_{n,\lambda} \mathbb{I}([n], -) J ′ ( X ′ ) = ∐ n , λ I ([ n ] , − ) . We check e e e is a superfluous epimorphism.
Epimorphism. It suffices to show e e e is pointwise surjective. Every z ∈ F ( D ) z \in\mathcal{F}(D) z ∈ F ( D ) has the form z = F ( i ) ( x ) z = \mathcal{F}(i)(x) z = F ( i ) ( x ) for some injection i : [ n ] ↪ D i: [n] \hookrightarrow D i : [ n ] ↪ D and x ∈ F ( [ n ] ) x \in\mathcal{F}([n]) x ∈ F ([ n ]) (e.g., taking n = ∣ D ∣ n = |D| n = ∣ D ∣ and i i i to be any bijection [ n ] → D [n] \to D [ n ] → D , an isomorphism in I \mathbb{I} I ); choosing n n n minimal forces x ∈ New n ( F ) x \in\operatorname{New}_n(\mathcal{F}) x ∈ New n ( F ) , and then z z z lies in the image of y λ y_\lambda y λ for the orbit λ ∋ x \lambda\ni x λ ∋ x .
Superfluous. Assume a subobject Z ⊆ J ′ ( X ′ ) Z \subseteq\mathcal{J}'(X') Z ⊆ J ′ ( X ′ ) has an epimorphism e ∣ Z e|_Z e ∣ Z ; we argue Z Z Z cannot be proper, so Z = J ′ ( X ′ ) Z = \mathcal{J}'(X') Z = J ′ ( X ′ ) . Subobjects of a coproduct in [ I , S e t ] [\mathbb{I},\mathbf{Set}] [ I , Set ] decompose componentwise, so if Z Z Z were proper then Z λ 0 ⊊ I ( [ n 0 ] , − ) Z_{\lambda_0} \subsetneq\mathbb{I}([n_0], -) Z λ 0 ⊊ I ([ n 0 ] , − ) for some component ( n 0 , λ 0 ) (n_0,\lambda_0) ( n 0 , λ 0 ) , whence Z λ 0 ( [ n 0 ] ) = ∅ Z_{\lambda_0}([n_0]) = \varnothing Z λ 0 ([ n 0 ]) = ∅ by Lemma D.2. Pick x 0 ∈ λ 0 ⊆ F ( [ n 0 ] ) x_0 \in\lambda_0 \subseteq\mathcal{F}([n_0]) x 0 ∈ λ 0 ⊆ F ([ n 0 ]) ; we check x 0 x_0 x 0 is not in the image of ( e ∣ Z ) [ n 0 ] (e|_Z)_{[n_0]} ( e ∣ Z ) [ n 0 ] . The image is the union over components ( n , λ ) (n,\lambda) ( n , λ ) of { F ( h ) ( x λ ) ∣ h ∈ Z λ ( [ n 0 ] ) } \{\mathcal{F}(h)(x_\lambda) \mid h \in Z_\lambda([n_0])\} { F ( h ) ( x λ ) ∣ h ∈ Z λ ([ n 0 ])} , and:
components with n < n 0 n < n_0 n < n 0 miss x 0 x_0 x 0 since x 0 ∈ New n 0 ( F ) x_0 \in\operatorname{New}_{n_0}(\mathcal{F}) x 0 ∈ New n 0 ( F ) ;
components with n > n 0 n > n_0 n > n 0 contribute nothing as I ( [ n ] , [ n 0 ] ) = ∅ \mathbb{I}([n],[n_0]) = \varnothing I ([ n ] , [ n 0 ]) = ∅ ;
components with n = n 0 n = n_0 n = n 0 and λ ≠ λ 0 \lambda\ne\lambda_0 λ = λ 0 produce elements of the S n 0 S_{n_0} S n 0 -orbit λ \lambda λ , which are disjoint from λ 0 ∋ x 0 \lambda_0 \ni x_0 λ 0 ∋ x 0 ;
and the component ( n 0 , λ 0 ) (n_0,\lambda_0) ( n 0 , λ 0 ) contributes nothing because Z λ 0 ( [ n 0 ] ) = ∅ Z_{\lambda_0}([n_0]) = \varnothing Z λ 0 ([ n 0 ]) = ∅ .
So x 0 x_0 x 0 is uncovered, contradicting that e ∣ Z e|_Z e ∣ Z is an epimorphism. Therefore Z = J ′ ( X ′ ) Z = \mathcal{J}'(X') Z = J ′ ( X ′ ) , i.e., e e e is superfluous. ◀
Theorem 4.3 (orbit-count preservation). Let X ∈ N o m X \in\mathbf{Nom} X ∈ Nom and let p : X ′ ↠ X p: X' \twoheadrightarrow X p : X ′ ↠ X be the equivariant surjection corresponding to the projective cover of J ( X ) \mathcal{J}(X) J ( X ) , as above. Then, orb ( p ) \operatorname{orb}(p) orb ( p ) is a dimension-preserving bijection, i.e., dim ( O ′ ) = dim ( orb ( p ) ( O ′ ) ) \dim(O') = \dim(\operatorname{orb}(p)(O')) dim ( O ′ ) = dim ( orb ( p ) ( O ′ )) for every orbit O ′ O' O ′ of X ′ X' X ′ .
Proof. We instantiate the construction of Theorem 4.2 at F = J ( X ) \mathcal{F} = \mathcal{J}(X) F = J ( X ) and read off its orbits: we identify the new elements at each level, construct a dimension-preserving bijection ϕ d \phi_d ϕ d between the orbits of X ′ X' X ′ and those of X X X , and finally check that this bijection is the one induced by p p p .
Apply the construction from the proof of Theorem 4.2 to F = J ( X ) \mathcal{F} = \mathcal{J}(X) F = J ( X ) , where J ( X ) ( C ) = { x ∈ X ∣ supp ( x ) ⊆ C } \mathcal{J}(X)(C) = \{x \in X \mid\operatorname{supp}(x) \subseteq C\} J ( X ) ( C ) = { x ∈ X ∣ supp ( x ) ⊆ C } , writing the dimension index as d d d . Since each Inj ( [ d ] , N ) \operatorname{Inj}([d],\mathbb{N}) Inj ([ d ] , N ) is a single orbit of dimension d d d , the orbits of X ′ = ∐ d , λ Inj ( [ d ] , N ) X' = \coprod_{d,\lambda} \operatorname{Inj}([d],\mathbb{N}) X ′ = ∐ d , λ Inj ([ d ] , N ) are exactly the summands O d , λ ′ ≅ Inj ( [ d ] , N ) O'_{d,\lambda} \cong\operatorname{Inj}([d],\mathbb{N}) O d , λ ′ ≅ Inj ([ d ] , N ) , one for each λ ∈ Λ d \lambda\in\Lambda_d λ ∈ Λ d , and dim ( O d , λ ′ ) = d \dim(O'_{d,\lambda}) = d dim ( O d , λ ′ ) = d . Unfolding J ( X ) \mathcal{J}(X) J ( X ) gives
New d ( J ( X ) ) = { x ∈ X ∣ supp ( x ) = [ d ] } , \operatorname{New}_d(\mathcal{J}(X)) = \{x \in X \mid\operatorname{supp}(x) = [d]\}, New d ( J ( X )) = { x ∈ X ∣ supp ( x ) = [ d ]} ,
the elements whose least support is exactly [ d ] [d] [ d ] .
Let M d M_d M d be the set of dimension-d d d orbits of X X X , and define ϕ d : Λ d → M d \phi_d: \Lambda_d \to M_d ϕ d : Λ d → M d by ϕ d ( S d ⋅ x ) = G ⋅ x \phi_d(S_d \cdot x) = G \cdot x ϕ d ( S d ⋅ x ) = G ⋅ x . We verify it is a well-defined bijection.
Well defined. supp ( x ) = [ d ] \operatorname{supp}(x) = [d] supp ( x ) = [ d ] gives dim ( G ⋅ x ) = d \dim(G \cdot x) = d dim ( G ⋅ x ) = d , and any x ′ ∈ S d ⋅ x x' \in S_d \cdot x x ′ ∈ S d ⋅ x has G ⋅ x ′ = G ⋅ x G \cdot x' = G \cdot x G ⋅ x ′ = G ⋅ x since S d ≤ G S_d \leq G S d ≤ G .
Injective. If g ⋅ x 1 = x 2 g \cdot x_1 = x_2 g ⋅ x 1 = x 2 with x 1 , x 2 ∈ New d ( J ( X ) ) x_1,x_2 \in\operatorname{New}_d(\mathcal{J}(X)) x 1 , x 2 ∈ New d ( J ( X )) , then g ( supp ( x 1 ) ) = supp ( x 2 ) g(\operatorname{supp}(x_1)) = \operatorname{supp}(x_2) g ( supp ( x 1 )) = supp ( x 2 ) gives g ( [ d ] ) = [ d ] g([d]) = [d] g ([ d ]) = [ d ] , so g ∣ [ d ] ∈ S d g|_{[d]} \in S_d g ∣ [ d ] ∈ S d ; since x 1 x_1 x 1 is supported by [ d ] [d] [ d ] , the action of g g g on x 1 x_1 x 1 depends only on its restriction g ∣ [ d ] g|_{[d]} g ∣ [ d ] , so ( g ∣ [ d ] ) ⋅ x 1 = g ⋅ x 1 = x 2 (g|_{[d]}) \cdot x_1 = g \cdot x_1 = x_2 ( g ∣ [ d ] ) ⋅ x 1 = g ⋅ x 1 = x 2 , hence S d ⋅ x 1 = S d ⋅ x 2 S_d \cdot x_1 = S_d \cdot x_2 S d ⋅ x 1 = S d ⋅ x 2 .
Surjective. Given μ ∈ M d \mu\in M_d μ ∈ M d and x ∈ μ x \in\mu x ∈ μ , some g ∈ G g \in G g ∈ G has g ( supp ( x ) ) = [ d ] g(\operatorname{supp}(x)) = [d] g ( supp ( x )) = [ d ] , so g ⋅ x ∈ New d ( J ( X ) ) ∩ μ g \cdot x \in\operatorname{New}_d(\mathcal{J}(X)) \cap\mu g ⋅ x ∈ New d ( J ( X )) ∩ μ and ϕ d ( S d ⋅ ( g ⋅ x ) ) = μ \phi_d(S_d \cdot(g \cdot x)) = \mu ϕ d ( S d ⋅ ( g ⋅ x )) = μ . Thus ϕ d \phi_d ϕ d is a bijection, and the orbits of X ′ X' X ′ biject with those of X X X dimension by dimension. It remains to identify p p p with ϕ d \phi_d ϕ d on orbits. The component y λ : I ( [ d ] , − ) → J ( X ) y_\lambda: \mathbb{I}([d], -) \to J(X) y λ : I ([ d ] , − ) → J ( X ) is Yoneda-induced by x λ ∈ λ x_\lambda\in\lambda x λ ∈ λ , so on an element i ∈ Inj ( [ d ] , N ) i \in\operatorname{Inj}([d], \mathbb{N}) i ∈ Inj ([ d ] , N ) of O d , λ ′ O'_{d,\lambda} O d , λ ′ it acts by y λ ( i ) = J ( X ) ( i ) ( x λ ) = i ^ ⋅ x λ y_\lambda(i) = J(X)(i)(x_\lambda) = \hat{i} \cdot x_\lambda y λ ( i ) = J ( X ) ( i ) ( x λ ) = i ^ ⋅ x λ , where i ^ ∈ G \hat{i} \in G i ^ ∈ G is any permutation extending i i i . As i i i ranges over Inj ( [ d ] , N ) \operatorname{Inj}([d], \mathbb{N}) Inj ([ d ] , N ) , the extension i ^ \hat{i} i ^ ranges over all of G G G , so the image is the whole orbit G ⋅ x λ = ϕ d ( λ ) G \cdot x_\lambda= \phi_d(\lambda) G ⋅ x λ = ϕ d ( λ ) . Hence p p p restricts to a surjection O d , λ ′ ↠ ϕ d ( λ ) O'_{d,\lambda} \twoheadrightarrow\phi_d(\lambda) O d , λ ′ ↠ ϕ d ( λ ) , so orb ( p ) = ∐ d ϕ d \operatorname{orb}(p) = \coprod_d \phi_d orb ( p ) = ∐ d ϕ d is a dimension-preserving bijection.
We conclude this appendix with the uniqueness of projective covers, used in § 4.1 and Lemma G.1 ; the standard argument applies verbatim in [ I , S e t ] [\mathbb{I}, \mathbf{Set}] [ I , Set ] .
Lemma D.3 (uniqueness of projective covers). Any two projective covers ( P , e ) (P,e) ( P , e ) and ( P ′ , e ′ ) (P',e') ( P ′ , e ′ ) of the same F ∈ [ I , S e t ] \mathcal{F} \in[\mathbb{I}, \mathbf{Set}] F ∈ [ I , Set ] are isomorphic via some φ : P → P ′ \varphi: P \to P' φ : P → P ′ with e ′ ∘ φ = e e' \circ\varphi= e e ′ ∘ φ = e .
Proof. Projectivity of P P P lifts e e e along the epimorphism e ′ e' e ′ to some φ \varphi φ with e ′ ∘ φ = e e' \circ\varphi= e e ′ ∘ φ = e . The image Im ( φ ) ⊆ P ′ \operatorname{Im}(\varphi) \subseteq P' Im ( φ ) ⊆ P ′ (computed pointwise) satisfies e ′ ( Im ( φ ) ) ⊇ Im ( e ) = F e'(\operatorname{Im}(\varphi)) \supseteq\operatorname{Im}(e) = \mathcal{F} e ′ ( Im ( φ )) ⊇ Im ( e ) = F , so superfluousness of e ′ e' e ′ forces Im ( φ ) = P ′ \operatorname{Im}(\varphi) = P' Im ( φ ) = P ′ , i.e., φ \varphi φ is an epimorphism. Projectivity of P ′ P' P ′ then yields ψ : P ′ → P \psi: P' \to P ψ : P ′ → P with φ ∘ ψ = id P ′ \varphi\circ\psi= \operatorname{id}_{P'} φ ∘ ψ = id P ′ , and e ∘ ψ = e ′ ∘ φ ∘ ψ = e ′ e \circ\psi= e' \circ\varphi\circ\psi= e' e ∘ ψ = e ′ ∘ φ ∘ ψ = e ′ , so the subobject Im ( ψ ) ⊆ P \operatorname{Im}(\psi) \subseteq P Im ( ψ ) ⊆ P maps onto F \mathcal{F} F via e e e ; superfluousness of e e e forces Im ( ψ ) = P \operatorname{Im}(\psi) = P Im ( ψ ) = P . Thus ψ \psi ψ is both an epimorphism and a monomorphism (being split by φ \varphi φ ), hence an isomorphism (isomorphisms in [ I , S e t ] [\mathbb{I}, \mathbf{Set}] [ I , Set ] are the pointwise bijections), and φ = ψ − 1 \varphi= \psi^{-1} φ = ψ − 1 is an isomorphism as well.
Proofs for Section 4.2
Theorem 4.4 (strong lifts of automata). Let A = ( Σ , Q , q 0 , δ , F ) \mathcal{A} = (\Sigma, Q, q_0, \delta, F) A = ( Σ , Q , q 0 , δ , F ) be a nominal automaton over a strong alphabet Σ \Sigma Σ , and let p : Q ′ ↠ Q p : Q' \twoheadrightarrow Q p : Q ′ ↠ Q be the equivariant surjection corresponding to the projective cover of J ( Q ) J(Q) J ( Q ) . Then, there exists a strong nominal automaton A ′ = ( Σ , Q ′ , q 0 ′ , δ ′ , F ′ ) \mathcal{A}' = (\Sigma, Q', q'_0, \delta', F') A ′ = ( Σ , Q ′ , q 0 ′ , δ ′ , F ′ ) for which p p p is an automaton homomorphism, that is, p ( q 0 ′ ) = q 0 p(q'_0) = q_0 p ( q 0 ′ ) = q 0 , F ′ = p − 1 ( F ) F' = p^{-1}(F) F ′ = p − 1 ( F ) , and p ( δ ′ ( q ′ , σ ) ) = δ ( p ( q ′ ) , σ ) p(\delta'(q', \sigma)) = \delta(p(q'), \sigma) p ( δ ′ ( q ′ , σ )) = δ ( p ( q ′ ) , σ ) for all q ′ ∈ Q ′ q' \in Q' q ′ ∈ Q ′ and σ ∈ Σ \sigma\in\Sigma σ ∈ Σ ; in particular, L ( A ′ ) = L ( A ) L(\mathcal{A}') = L(\mathcal{A}) L ( A ′ ) = L ( A ) .
Proof. By Theorem 4.2, Q ′ Q' Q ′ is strong. Set F ′ = p − 1 ( F ) F' = p^{-1}(F) F ′ = p − 1 ( F ) . Since q 0 q_0 q 0 has empty support, its orbit is a singleton; by Theorem 4.3, the corresponding orbit in Q ′ Q' Q ′ also has dimension 0 0 0 and thus consists of a single element, which we denote q 0 ′ q'_0 q 0 ′ , with p ( q 0 ′ ) = q 0 p(q'_0) = q_0 p ( q 0 ′ ) = q 0 and supp ( q 0 ′ ) = ∅ \operatorname{supp}(q'_0) = \varnothing supp ( q 0 ′ ) = ∅ . Since Σ \Sigma Σ is strong by assumption and Q ′ Q' Q ′ is strong, their product Q ′ × Σ Q' \times\Sigma Q ′ × Σ is strong (applying Lemma C.1 orbitwise), so J ′ ( Q ′ × Σ ) J'(Q' \times\Sigma) J ′ ( Q ′ × Σ ) is projective in [ I , S e t ] [\mathbb{I}, \mathbf{Set}] [ I , Set ] by Theorem 3.4; hence the map J ( δ ∘ ( p × id Σ ) ) J(\delta\circ(p \times\operatorname{id}_\Sigma)) J ( δ ∘ ( p × id Σ )) lifts along the epimorphism J ( p ) = e : J ( Q ′ ) ↠ J ( Q ) J(p) = e : J(Q') \twoheadrightarrow J(Q) J ( p ) = e : J ( Q ′ ) ↠ J ( Q ) , and by full faithfulness of J ′ J' J ′ , this yields an equivariant δ ′ : Q ′ × Σ → Q ′ \delta' : Q' \times\Sigma\to Q' δ ′ : Q ′ × Σ → Q ′ satisfying p ∘ δ ′ = δ ∘ ( p × id Σ ) p \circ\delta' = \delta\circ(p \times\operatorname{id}_\Sigma) p ∘ δ ′ = δ ∘ ( p × id Σ ) . Hence p p p is an automaton homomorphism. A standard induction on words shows p ( δ ′ ∗ ( q 0 ′ , w ) ) = δ ∗ ( q 0 , w ) p(\delta'^*(q'_0,w)) = \delta^*(q_0,w) p ( δ ′ ∗ ( q 0 ′ , w )) = δ ∗ ( q 0 , w ) ; since F ′ = p − 1 ( F ) F' = p^{-1}(F) F ′ = p − 1 ( F ) , this gives δ ′ ∗ ( q 0 ′ , w ) ∈ F ′ ⟺ δ ∗ ( q 0 , w ) ∈ F \delta'^*(q'_0,w) \in F' \Longleftrightarrow\delta^*(q_0,w) \in F δ ′ ∗ ( q 0 ′ , w ) ∈ F ′ ⟺ δ ∗ ( q 0 , w ) ∈ F , confirming L ( A ′ ) = L ( A ) L(\mathcal{A}') = L(\mathcal{A}) L ( A ′ ) = L ( A ) .
Effective Operations on the Array Representation
We summarize the computational costs of the effective operations on orbit-finite strong nominal sets, which were introduced in Section 3.2. This analysis parallels that of [40 Sec. 8] for the total-order symmetry.
We adopt the constant-time assumption on orbit-level primitives from Section 5, as in [40 ] . By representing an equivariant set as a hash set of its orbits and an equivariant map as a per-orbit index array (as detailed in Section 3.2), we can efficiently implement these operations. We assume that user-supplied predicates and maps evaluate in O ( 1 ) O(1) O ( 1 ) time. The costs are then as given in Table 4 .
Table 4. Costs of the effective operations on orbit-finite strong nominal sets defined in § 3.2 , expressed in the orbit counts N ( ⋅ ) N(\cdot) N ( ⋅ ) and dimensions dim ( ⋅ ) \dim(\cdot) dim ( ⋅ ) of the operands; β \beta β is the product-orbit count of Proposition 3.5 . Orbit-level primitives are assumed constant-time as in § 5 ; bounds relying on hashing are expected time.
By storing orbit representations in a hash set rather than an ordered tree, we achieve expected-O ( 1 ) O(1) O ( 1 ) membership tests and sorting-free image computations, in contrast to the (worst-case) O ( log N ( X ) ) O(\log N(X)) O ( log N ( X )) and O ( N ( X ) log N ( X ) ) O(N(X)\log N(X)) O ( N ( X ) log N ( X )) tree bounds of [40 ] . The only factorial cost is the product: by Proposition 3.5 , two single orbits of dimensions m m m and n n n yield β ( m , n ) \beta(m,n) β ( m , n ) orbits, each built in O ( 1 ) O(1) O ( 1 ) from its partial bijection. This is the same factor β \beta β appearing in the costs of the algorithms of § 5 .
The constant-time assumption on orbit-level primitives is an idealization, and its gap to actual costs is not always negligible. Constructing the orbit of a concrete element scans its entire representation: for a word w ∈ Σ ∗ w \in\Sigma^* w ∈ Σ ∗ of length ℓ \ell ℓ , whose dimension may reach ℓ ⋅ dim ( Σ ) \ell\cdot\dim(\Sigma) ℓ ⋅ dim ( Σ ) , the scan takes Ω ( ℓ ) \Omega(\ell) Ω ( ℓ ) time. Learning is particularly exposed to this gap, as the observation table is indexed by words: filling a cell computes the orbit of a word of length O ( ℓ ) O(\ell) O ( ℓ ) for ℓ = m + O ( n d ) \ell= m + O(nd) ℓ = m + O ( n d ) as in Theorem 5.4, and each membership query transmits such a word, so the actual running time carries a factor of ℓ \ell ℓ that the model hides and that is not easily avoided. In our experience developing Namae, orbit construction and representative selection were among the most performance-critical operations: deriving orbit construction for lists generically from their algebraic structure Nil | Cons( x , x s ) (x,xs) ( x , x s ) computes a coincidence pattern of the pair ( x , x s ) (x,xs) ( x , x s ) at every step and is therefore quadratic in the length ℓ \ell ℓ , so Namae instead builds the orbit of a word by a single flat scan.
Proofs and Pseudocode for Language Equivalence
The generating system. Let X X X be an orbit-finite strong nominal set with orbits O 1 , … , O N O_1,\ldots,O_N O 1 , … , O N , where O i ≅ Inj ( [ d i ] , N ) O_i \cong\operatorname{Inj}([d_i],\mathbb{N}) O i ≅ Inj ([ d i ] , N ) ; we identify elements of O i O_i O i with injective arrays x : [ d i ] → N x\colon[d_i] \to\mathbb{N} x : [ d i ] → N . A generating system G \mathcal{G} G represents an equivariant equivalence relation ∼ \sim ∼ on X X X using the following data, generalizing the register-level structures of [27 , 28 , 30 ] to orbit-finite strong nominal sets:
a partition of the orbit indices { 1 , … , N } \{1,\ldots,N\} { 1 , … , N } into classes, mapping each orbit to its class representative to track ∼ \sim ∼ -related orbits;
for each class representative r r r , a characteristic set χ r ⊆ [ d r ] \chi_r \subseteq[d_r] χ r ⊆ [ d r ] and a generating set G r G_r G r for a subgroup ⟨ G r ⟩ ≤ Sym ( χ r ) \langle G_r\rangle\leq\operatorname{Sym}(\chi_r) ⟨ G r ⟩ ≤ Sym ( χ r ) ;
for each orbit O i O_i O i in the class of r r r , an injection (termed a ray ) ρ i : χ r ↪ [ d i ] \rho_i\colon\chi_r \hookrightarrow[d_i] ρ i : χ r ↪ [ d i ] aligning the characteristic positions with those of O i O_i O i .
Algorithm 1 The merge operation of a generating system
Input: elements $x \in O_i$ and $y \in O_j$
$s \gets$ the coincidence pattern of $(x,y)$: the partial bijection with $s(a)=b \Longleftrightarrow x(a)=y(b)$;
if $O_i$ and $O_j$ lie in the same class $r$ then
$\sigma \gets \rho_i\,;\,s\,;\,\rho_j^{-1}$; // transported pattern, a partial bijection on $\chi_r$
if $\operatorname{dom}(\sigma)=\chi_r$ then
$G_r \gets G_r \cup \{\sigma\}$; // generator addition
else
$\chi' \gets \operatorname{base}(\chi_r;\{\sigma\}\cup G_r)$; // shrink
$G_r \gets \{g|_{\chi'}:g\in\{\sigma\}\cup G_r,\ g|_{\chi'}\in\operatorname{Sym}(\chi')\}$; $\chi_r \gets \chi'$;
restrict every ray of class $r$ to $\chi'$;
else
let $r_1,r_2$ be the classes of $O_i,O_j$; // fusion
$\sigma_1 \gets \rho_i\,;\,s\,;\,\rho_j^{-1}$; $\sigma_2 \gets \rho_j\,;\,s^{-1}\,;\,\rho_i^{-1}$;
$H \gets \{\sigma_1;\sigma_2\}\cup G_{r_1}\cup\{\sigma_1;g;\sigma_2:g\in G_{r_2}\}$;
$\chi \gets \operatorname{base}(\chi_{r_1};H)$;
unite the two classes with representative $r_1$;
$G_{r_1} \gets \{h|_\chi:h\in H,\ h|_\chi\in\operatorname{Sym}(\chi)\}$; $\chi_{r_1}\gets\chi$;
restrict every ray of class $r_1$ to $\chi$, and replace every ray $\rho_k$ of class $r_2$ by $(\sigma_1;\rho_k)|_\chi$;
This data represents the relation
x ∼ y ⟺ O i , O j lie in the same class r , and x ∘ ρ i ∘ σ = y ∘ ρ j for some σ ∈ ⟨ G r ⟩ , (2) x \sim y \Longleftrightarrow O_i,O_j\text{ lie in the same class }r,\text{ and }x\circ\rho_i\circ\sigma=y\circ\rho_j\text{ for some }\sigma\in\langle G_r\rangle, \tag*{(2)} x ∼ y ⟺ O i , O j lie in the same class r , and x ∘ ρ i ∘ σ = y ∘ ρ j for some σ ∈ ⟨ G r ⟩ , (2)
for x ∈ O i x\in O_i x ∈ O i and y ∈ O j y\in O_j y ∈ O j , where x ∘ ρ i ∈ Inj ( χ r , N ) x\circ\rho_i\in\operatorname{Inj}(\chi_r,\mathbb{N}) x ∘ ρ i ∈ Inj ( χ r , N ) lists the characteristic atoms of x x x . In [28 ] , the global freshness of fresh-register automata is additionally handled by indexing the structure with history levels and by freshness-aware bisimulation conditions [28 Defs. 10 and 18] , orthogonally to the per-level group-theoretic representation generalized here.
The operations create, contains, and classes maintain this data directly: create( X ) (X) ( X ) makes each orbit a singleton class with χ i = [ d i ] \chi_i=[d_i] χ i = [ d i ] , trivial group, and identity ray; contains( x , y ) (x,y) ( x , y ) transports the coincidence pattern of ( x , y ) (x,y) ( x , y ) to χ r \chi_r χ r and tests membership in ⟨ G r ⟩ \langle G_r\rangle ⟨ G r ⟩ ; and classes reads off the classes with their characteristic tuples. The one nontrivial operation is merge, shown in Algorithm 1. Writing f ; g f\,;\,g f ; g for the partial-bijection composite that applies f f f then g g g , merge( x , y ) (x,y) ( x , y ) forms the coincidence pattern s s s of ( x , y ) (x,y) ( x , y ) (the partial bijection matching equal atoms), transports it to the characteristic set along the rays, and coarsens ∼ \sim ∼ by one of three updates: a generator addition when the transported pattern is a permutation of χ r \chi_r χ r , a characteristic-set shrink when it is partial, or a class fusion when x x x and y y y start in different classes. The shrink recomputes χ r \chi_r χ r as base ( χ r ; { σ } ∪ G r ) \operatorname{base}(\chi_r;\{\sigma\}\cup G_r) base ( χ r ; { σ } ∪ G r ) , the largest Δ ⊆ χ r \Delta\subseteq\chi_r Δ ⊆ χ r on which the transported pattern σ \sigma σ and the generators all restrict to permutations of Δ \Delta Δ ; this is the base of [28 Lem. 23] , computable by the graph reachability of [28 Lem. 24] .
The following lemma is our analogue of the invariants of [28 Sec. 4] ; it makes the generalization precise and identifies the classes output with the strong approximation. Its proof follows the forcing scheme of [28 Sec. 4] ; what is new is the transport across orbits of different dimensions, via rays and fresh atoms, and the identification with the projective cover.
Lemma G.1 (generating-system invariant).
For any generating-system data, the relation ∼ \sim ∼ of (2) is an equivariant equivalence relation on X X X .
After create(X X X ) followed by any sequence of operations merge(x 1 , y 1 x_1,y_1 x 1 , y 1 ), …, merge(x k , y k x_k,y_k x k , y k ), the represented relation ∼ \sim ∼ is the finest equivariant equivalence relation on X X X relating x l x_l x l and y l y_l y l for all l ≤ k l \le k l ≤ k .
classes returns the strong nominal set P = ∐ r Inj ( [ ∣ χ r ∣ ] , N ) P = \coprod_r \operatorname{Inj}([\lvert\chi_r\rvert],\mathbb{N}) P = ∐ r Inj ([∣ χ r ∣] , N ) , one orbit per class, together with the equivariant surjection h : X ↠ P h:X \twoheadrightarrow P h : X ↠ P sending each x x x to its characteristic tuple x ∘ ρ i x \circ\rho_i x ∘ ρ i (composed with a renaming χ r ≅ [ ∣ χ r ∣ ] \chi_r \cong[\lvert\chi_r\rvert] χ r ≅ [∣ χ r ∣] fixed once per class). Then P P P corresponds to the projective cover of J ( X / ∼ ) J(X/{\sim}) J ( X / ∼ ) (unique by Lemma D.3), and h h h lifts the quotient map q : X → X / ∼ q:X \to X/{\sim} q : X → X / ∼ : p ∘ h = q p \circ h = q p ∘ h = q for the equivariant surjection p : P ↠ X / ∼ p:P \twoheadrightarrow X/{\sim} p : P ↠ X / ∼ corresponding to the cover.
Invariants 1 and 3 are proved directly below; for the minimality half of Invariant 2, we first extract the recurring arguments as standalone lemmas, following this strategy. Each elementary step of Algorithm 1 replaces the data ( χ r , G r ) (\chi_r,G_r) ( χ r , G r ) of the affected class by ( χ ′ , S ∣ χ ′ ) (\chi',S|_{\chi'}) ( χ ′ , S ∣ χ ′ ) , where S S S is a set of transported patterns and χ ′ = base ( χ r ; S ) \chi'=\operatorname{base}(\chi_r;S) χ ′ = base ( χ r ; S ) , so that the post-step relation relates exactly the pairs whose χ ′ \chi' χ ′ -tuples differ by a twist in ⟨ S ∣ χ ′ ⟩ \langle S|_{\chi'}\rangle ⟨ S ∣ χ ′ ⟩ . Minimality therefore reduces to showing that any equivariant equivalence relation ≈ \approx ≈ relating a witnessing pair for each pattern in S S S , in the sense of realization defined below, must relate all these twisted pairs; this is Lemma G.4. Its proof moves the atoms of an element outside its χ ′ \chi' χ ′ -positions freely, which is sound because ≈ \approx ≈ cannot separate elements by those atoms; Lemma G.3 establishes this by confining the supports of ≈ \approx ≈ -classes to χ ′ \chi' χ ′ -atoms. Both rest on Lemma G.2, which transfers characteristic tuples freely across the orbits of a class.
The lemmas concern a fixed generating-system state representing ∼ \sim ∼ and a class r r r . For an element u ∈ O k u \in O_k u ∈ O k of the class and Δ ⊆ χ r \Delta\subseteq\chi_r Δ ⊆ χ r , the Δ \Delta Δ -tuple of u u u is the restriction ( u ∘ ρ k ) ∣ Δ (u \circ\rho_k)|_\Delta ( u ∘ ρ k ) ∣ Δ of its characteristic tuple, and the Δ \Delta Δ -atoms of u u u are the entries u ( ρ k ( c ) ) u(\rho_k(c)) u ( ρ k ( c )) for c ∈ Δ c \in\Delta c ∈ Δ ; in particular, the χ r \chi_r χ r -tuple is the characteristic tuple, and the χ r \chi_r χ r -atoms are the characteristic atoms.
Lemma G.2 (tuple transfer). Let O k O_k O k be an orbit of class r r r .
Every t ∈ Inj ( χ r , N ) t \in\operatorname{Inj}(\chi_r,\mathbb{N}) t ∈ Inj ( χ r , N ) is the characteristic tuple of some v ∈ O k v \in O_k v ∈ O k , whose remaining entries can be chosen fresh for any prescribed finite set of atoms.
Any u , v u,v u , v in the class with equal characteristic tuples satisfy u ∼ v u \sim v u ∼ v .
Proof. For (1), extend t t t to an injective array of dimension d k d_k d k by filling the positions outside the ray image with pairwise distinct atoms avoiding t t t and the prescribed set; every injective array of that dimension lies in O k O_k O k . For (2), equal characteristic tuples satisfy Equation (2) with the identity twist. ◀
For an equivariant equivalence relation ≈ \approx ≈ on X X X , we say a pair u ≈ v u \approx v u ≈ v , with u ∈ O k u \in O_k u ∈ O k and v ∈ O l v \in O_l v ∈ O l in the class, realizes a partial bijection τ \tau τ on χ r \chi_r χ r if the characteristic tuples of u u u and v v v agree exactly along τ \tau τ : u ( ρ k ( τ ( c ) ) ) = v ( ρ l ( c ) ) u(\rho_k(\tau(c))) = v(\rho_l(c)) u ( ρ k ( τ ( c ))) = v ( ρ l ( c )) for every c ∈ dom ( τ ) c \in\operatorname{dom}(\tau) c ∈ dom ( τ ) , and no further χ r \chi_r χ r -atoms of u u u and v v v coincide. If ( u , v ) (u,v) ( u , v ) realizes τ \tau τ , then ( v , u ) (v,u) ( v , u ) realizes τ − 1 \tau^{-1} τ − 1 ; since base and generated subgroups are unchanged under inverting their arguments, we use realizing pairs in either orientation. If ≈ \approx ≈ contains ∼ \sim ∼ , every g ∈ ⟨ G r ⟩ g \in\langle G_r\rangle g ∈ ⟨ G r ⟩ is realized: given any u ∈ O k u \in O_k u ∈ O k , Lemma G.2(1) provides v ∈ O k v \in O_k v ∈ O k with v ∘ ρ k = u ∘ ρ k ∘ g v \circ\rho_k = u \circ\rho_k \circ g v ∘ ρ k = u ∘ ρ k ∘ g and fresh remaining entries, so u ∼ v u \sim v u ∼ v and the characteristic coincidences are exactly those matched by g g g .
Lemma G.3 (support confinement). Let ≈ \approx ≈ be an equivariant equivalence relation on X X X containing ∼ \sim ∼ , let S S S be a set of partial bijections on χ r \chi_r χ r , each realized by some ≈ \approx ≈ -pair in the class, and let χ ′ = base ( χ r ; S ) \chi'=\operatorname{base}(\chi_r;S) χ ′ = base ( χ r ; S ) . Then supp ( [ u ] ≈ ) \operatorname{supp}([u]_\approx) supp ([ u ] ≈ ) consists of χ ′ \chi' χ ′ -atoms of u u u , for every u u u in the class.
Proof. Confinement to χ r \chi_r χ r . A permutation fixing the χ r \chi_r χ r -atoms of u u u fixes its characteristic tuple, so it maps u u u to a ∼ \sim ∼ -related element by Lemma G.2(2) and therefore stabilizes [ u ] ≈ [u]_{\approx} [ u ] ≈ ; hence supp ( [ u ] ≈ ) \operatorname{supp}([u]_{\approx}) supp ([ u ] ≈ ) consists of χ r \chi_r χ r -atoms of u u u .
Position constancy. Let D u = { c ∈ χ r : u ( ρ k ( c ) ) ∈ supp ( [ u ] ≈ ) } D_u = \{c \in\chi_r : u(\rho_k(c)) \in\operatorname{supp}([u]_{\approx})\} D u = { c ∈ χ r : u ( ρ k ( c )) ∈ supp ([ u ] ≈ )} collect the positions of the support in u u u . Acting by π ∈ G \pi\in G π ∈ G moves the support supp ( [ π ⋅ u ] ≈ ) = π ⋅ supp ( [ u ] ≈ ) \operatorname{supp}([\pi\cdot u]_{\approx}) = \pi\cdot\operatorname{supp}([u]_{\approx}) supp ([ π ⋅ u ] ≈ ) = π ⋅ supp ([ u ] ≈ ) and the entries together, so D π ⋅ u = D u D_{\pi\cdot u} = D_u D π ⋅ u = D u ; and equal-tuple elements share both their ≈ \approx ≈ -class and their characteristic tuple, so their position sets agree as well. Since an equal-tuple hop via Lemma G.2(1) followed by a G G G -move connects any two elements of the class, all position sets equal one set D D D .
Invariance under S S S . Let ( u 1 , v 1 ) (u_1,v_1) ( u 1 , v 1 ) realize τ ∈ S \tau\in S τ ∈ S . The atoms of supp ( [ u 1 ] ≈ ) = supp ( [ v 1 ] ≈ ) \operatorname{supp}([u_1]_{\approx}) = \operatorname{supp}([v_1]_{\approx}) supp ([ u 1 ] ≈ ) = supp ([ v 1 ] ≈ ) are χ r \chi_r χ r -atoms of both u 1 u_1 u 1 and v 1 v_1 v 1 by confinement, hence matched by the pattern τ \tau τ ; reading off their positions gives D ⊆ dom ( τ ) D \subseteq\operatorname{dom}(\tau) D ⊆ dom ( τ ) and τ ( D ) = D \tau(D) = D τ ( D ) = D by constancy.
Descent. Every τ ∈ S \tau\in S τ ∈ S thus restricts to a permutation of D D D , so D D D is contained in the largest such subset, χ ′ = base ( χ r ; S ) \chi' = \operatorname{base}(\chi_r; S) χ ′ = base ( χ r ; S ) .
Lemma G.4 (forcing). Under the hypotheses of Lemma G.3, with χ ′ \chi' χ ′ as there, any u , v u,v u , v in the class whose χ ′ \chi' χ ′ -tuples differ by a twist in ⟨ S ∣ χ ′ ⟩ \langle S|_{\chi'}\rangle ⟨ S ∣ χ ′ ⟩ , i.e., ( u ∘ ρ k ) ∣ χ ′ ∘ τ = ( v ∘ ρ l ) ∣ χ ′ (u \circ\rho_k)|_{\chi'} \circ\tau= (v \circ\rho_l)|_{\chi'} ( u ∘ ρ k ) ∣ χ ′ ∘ τ = ( v ∘ ρ l ) ∣ χ ′ for some τ ∈ ⟨ S ∣ χ ′ ⟩ \tau\in\langle S|_{\chi'}\rangle τ ∈ ⟨ S ∣ χ ′ ⟩ , satisfy u ≈ v u \approx v u ≈ v .
Proof.
Equal tuples (τ = id \tau= \operatorname{id} τ = id ). Since u u u and v v v may lie in different orbits, and Lemma G.2(2) requires equal full characteristic tuples, we route through fresh intermediates: by Lemma G.2(1), let w w w , in u u u ’s orbit, carry a characteristic tuple agreeing with u u u ’s on χ ′ \chi' χ ′ and fresh elsewhere, and let w ′ w' w ′ , in v v v ’s orbit, carry the same characteristic tuple as w w w and fresh remaining entries. The permutation fixing the χ ′ \chi' χ ′ -atoms of u u u and moving its remaining atoms to the fresh ones maps u u u to w w w and fixes [ u ] ≈ [u]_{\approx} [ u ] ≈ by Lemma G.3, so u ≈ w u \approx w u ≈ w ; likewise v ≈ w ′ v \approx w' v ≈ w ′ ; and w ∼ w ′ w \sim w' w ∼ w ′ by Lemma G.2(2), so u ≈ v u \approx v u ≈ v by transitivity.
A single generator. Let the χ ′ \chi' χ ′ -tuples differ by τ ∣ χ ′ \tau|_{\chi'} τ ∣ χ ′ for a single τ ∈ S \tau\in S τ ∈ S , realized by ( u 1 , v 1 ) (u_1,v_1) ( u 1 , v 1 ) . Transporting the pair by equivariance so that the χ ′ \chi' χ ′ -tuple of u 1 u_1 u 1 matches that of u u u , the equal-tuple case applies on both sides: u ≈ u 1 ≈ v 1 ≈ v u \approx u_1 \approx v_1 \approx v u ≈ u 1 ≈ v 1 ≈ v .
General twists. A twist in ⟨ S ∣ χ ′ ⟩ \langle S|_{\chi'}\rangle ⟨ S ∣ χ ′ ⟩ factors as a composite of generators and their inverses; interpolating elements that carry the intermediate χ ′ \chi' χ ′ -tuples, via Lemma G.2(1), and chaining the previous case, applied to the swapped realizing pair for inverse hops, gives u ≈ v u \approx v u ≈ v by transitivity.
Proof of Lemma G.1. We establish each claim in turn.
Proof of Invariant 1. Reflexivity and symmetry hold via σ = id \sigma= \operatorname{id} σ = id and σ − 1 \sigma^{-1} σ − 1 . For transitivity, x ∘ ρ i ∘ σ = y ∘ ρ j x \circ\rho_i \circ\sigma= y \circ\rho_j x ∘ ρ i ∘ σ = y ∘ ρ j and y ∘ ρ j ∘ σ ′ = z ∘ ρ k y \circ\rho_j \circ\sigma' = z \circ\rho_k y ∘ ρ j ∘ σ ′ = z ∘ ρ k give z ∘ ρ k = x ∘ ρ i ∘ ( σ ′ ∘ σ ) z \circ\rho_k = x \circ\rho_i \circ(\sigma' \circ\sigma) z ∘ ρ k = x ∘ ρ i ∘ ( σ ′ ∘ σ ) with σ ′ ∈ ⟨ G r ⟩ \sigma' \in\langle G_r\rangle σ ′ ∈ ⟨ G r ⟩ . For equivariance, acting by π ∈ G \pi\in G π ∈ G reinterprets the array x x x by π ∘ x \pi\circ x π ∘ x , so the defining equation is preserved: ( π ∘ x ) ∘ ρ i ∘ σ = ( π ∘ y ) ∘ ρ j (\pi\circ x) \circ\rho_i \circ\sigma= (\pi\circ y) \circ\rho_j ( π ∘ x ) ∘ ρ i ∘ σ = ( π ∘ y ) ∘ ρ j .
Proof of Invariant 2. create ( X ) \operatorname{create}(X) create ( X ) initializes singleton classes with χ i = [ d i ] \chi_i = [d_i] χ i = [ d i ] , trivial groups, and identity rays; by (2) this represents equality, the finest equivariant equivalence relation. merge ( x , y ) \operatorname{merge}(x,y) merge ( x , y ) of Algorithm 1 coarsens the represented relation by elementary steps until x ∼ y x \sim y x ∼ y holds: a class fusion when the two orbits lie in different classes, a generator addition when the transported pattern σ \sigma σ is a permutation of χ r \chi_r χ r , or a characteristic-set shrink that sets χ r \chi_r χ r to base ( χ r ; { σ } ∪ G r ) \operatorname{base}(\chi_r; \{\sigma\} \cup G_r) base ( χ r ; { σ } ∪ G r ) when σ \sigma σ is partial. Each elementary step only coarsens the represented relation, and afterwards x ∼ y x \sim y x ∼ y holds by construction, so the final relation is an equivariant equivalence relation (by Invariant 1) relating all merged pairs.
For minimality, let ≈ \approx ≈ be any equivariant equivalence relation with x l ≈ y l x_l \approx y_l x l ≈ y l for all l l l ; we show by induction over elementary steps that the represented relation stays contained in ≈ \approx ≈ . This holds after create. Consider a step triggered by merge(x,y), where x ≈ y x \approx y x ≈ y and, inductively, the pre-step relation ∼ \sim ∼ is contained in ≈ \approx ≈ ; Lemmas G.2 –G.4 then apply to this ∼ \sim ∼ and ≈ \approx ≈ .
Generator additions and shrinks. These replace ( χ r , G r ) (\chi_r,G_r) ( χ r , G r ) by ( χ ′ , ( { σ } ∪ G r ) ∣ χ ′ ) (\chi',(\{\sigma\}\cup G_r)|_{\chi'}) ( χ ′ , ({ σ } ∪ G r ) ∣ χ ′ ) for χ ′ = base ( χ r ; { σ } ∪ G r ) \chi' = \operatorname{base}(\chi_r;\{\sigma\}\cup G_r) χ ′ = base ( χ r ; { σ } ∪ G r ) ; when σ \sigma σ is total, χ ′ = χ r \chi'=\chi_r χ ′ = χ r and the step is a generator addition. The post-step relation relates exactly the pairs of the class whose χ ′ \chi' χ ′ -tuples differ by a twist in ⟨ ( { σ } ∪ G r ) ∣ χ ′ ⟩ \langle(\{\sigma\}\cup G_r)|_{\chi'}\rangle ⟨({ σ } ∪ G r ) ∣ χ ′ ⟩ , and each member of S = { σ } ∪ G r S=\{\sigma\}\cup G_r S = { σ } ∪ G r is realized by an ≈ \approx ≈ -pair: the pair ( y , x ) (y,x) ( y , x ) realizes σ \sigma σ , as σ \sigma σ is exactly the transported characteristic pattern of the merged pair, and the pre-step relation realizes each g ∈ G r g\in G_r g ∈ G r , as noted after Lemma G.2 . Hence Lemma G.4 forces every post-step pair.
Fusions. Relating x ≈ y x\approx y x ≈ y across two classes merges their ≈ \approx ≈ -connected components, so uniting the classes is forced, and the pairs represented afterwards are exactly the ⟨ H ∣ χ ⟩ \langle H\mid\chi\rangle ⟨ H ∣ χ ⟩ -twists, along the new rays, of tuple-equal pairs, for χ = base ( χ r 1 ; H ) \chi=\operatorname{base}(\chi_{r_1};H) χ = base ( χ r 1 ; H ) . The transported rays ( σ 1 ; ρ k ) ∣ χ (\sigma_1;\rho_k)|_\chi ( σ 1 ; ρ k ) ∣ χ are total and injective since χ ⊆ dom ( σ 1 ) \chi\subseteq\operatorname{dom}(\sigma_1) χ ⊆ dom ( σ 1 ) : H H H contains σ 1 ; σ 2 \sigma_1;\sigma_2 σ 1 ; σ 2 , the partial identity on dom ( σ 1 ) \operatorname{dom}(\sigma_1) dom ( σ 1 ) , and every member of H H H restricts to a permutation of χ \chi χ by the definition of base. Each member of H H H is realized by an ≈ \approx ≈ -pair: each g ′ ∈ G r 1 g'\in G_{r_1} g ′ ∈ G r 1 by the pre-step relation, as before; and a conjugate σ 1 ; g ; σ 2 \sigma_1;g;\sigma_2 σ 1 ; g ; σ 2 with g ∈ G r 2 g\in G_{r_2} g ∈ G r 2 by ( x , π ⋅ x ) (x,\pi\cdot x) ( x , π ⋅ x ) , where π ∈ G \pi\in G π ∈ G realizes the g g g -twist of y y y and moves the atoms of x x x outside the characteristic atoms of y y y to fresh ones, so that x ≈ y ≈ π ⋅ y ≈ π ⋅ x x\approx y\approx\pi\cdot y\approx\pi\cdot x x ≈ y ≈ π ⋅ y ≈ π ⋅ x by the inductive hypothesis and equivariance, and the characteristic tuples of x x x and π ⋅ x \pi\cdot x π ⋅ x agree exactly along σ 1 ; g ; σ 2 \sigma_1;g;\sigma_2 σ 1 ; g ; σ 2 (travel along σ 1 \sigma_1 σ 1 , twist by g g g , return along σ 2 \sigma_2 σ 2 ); g = id g=\operatorname{id} g = id covers σ 1 ; σ 2 \sigma_1;\sigma_2 σ 1 ; σ 2 . The arguments of Lemmas G.3 and G.4 then run over the united class with S = H S=H S = H and the new rays, with the uses of Lemma G.2 (2) adjusted to cross the old class boundary as follows. For confinement, stage 1 runs per old class and confines supports to the old characteristic atoms on each side; invariance under the realized σ 1 ; σ 2 \sigma_1;\sigma_2 σ 1 ; σ 2 then places the position set D D D inside dom ( σ 1 ) \operatorname{dom}(\sigma_1) dom ( σ 1 ) , so supports consist of atoms shared along the bridge, and transporting positions through σ 1 \sigma_1 σ 1 extends position constancy to the r 2 r_2 r 2 side. In the equal-tuple stage of Lemma G.4 , a cross-boundary pair u u u , on the r 1 r_1 r 1 side, and v v v , on the r 2 r_2 r 2 side, with equal χ \chi χ -tuples along the new rays is connected by the chain u ≈ w ∼ π ′ ⋅ x ≈ π ′ ⋅ y ∼ w ′ ≈ v u\approx w\sim\pi'\cdot x\approx\pi'\cdot y\sim w'\approx v u ≈ w ∼ π ′ ⋅ x ≈ π ′ ⋅ y ∼ w ′ ≈ v : the fresh intermediates w w w and w ′ w' w ′ are as in Lemma G.4 , π ′ \pi' π ′ is chosen so that π ′ ⋅ x \pi'\cdot x π ′ ⋅ x carries the full χ r 1 \chi_{r_1} χ r 1 -tuple of u u u and the remaining characteristic atoms of y y y go to fresh ones, and w ′ w' w ′ carries the full χ r 2 \chi_{r_2} χ r 2 -tuple of π ′ ⋅ y \pi'\cdot y π ′ ⋅ y ; the two ∼ \sim ∼ -hops are old-relation equal-tuple pairs, and the outer hops are the fresh-intermediate moves of Lemma G.4 . Hence every post-step pair is forced.
Hence the final represented relation is contained in every such ≈ \approx ≈ , and is therefore the finest one.
Proof of Invariant 3. By Equation (2) , q ( x ) q(x) q ( x ) is determined by, and determines, the class r r r of x x x 's orbit together with the coset [ x ∘ ρ i ] ∈ Inj ( χ r , N ) / ⟨ G r ⟩ [x\circ\rho_i]\in\operatorname{Inj}(\chi_r,\mathbb{N})/\langle G_r\rangle [ x ∘ ρ i ] ∈ Inj ( χ r , N ) / ⟨ G r ⟩ , so
X / ∼ ≅ ∐ r Inj ( χ r , N ) / ⟨ G r ⟩ X/{\sim}\cong\coprod_r \operatorname{Inj}(\chi_r,\mathbb{N})/\langle G_r\rangle X / ∼ ≅ r ∐ Inj ( χ r , N ) / ⟨ G r ⟩
an orbit-finite nominal set with one orbit per class, whose r r r -th orbit has support representation ( χ r , ⟨ G r ⟩ ) (\chi_r,\langle G_r\rangle) ( χ r , ⟨ G r ⟩) . By Theorem 4.3, the projective cover of J ( X / ∼ ) J(X/{\sim}) J ( X / ∼ ) has exactly one orbit per class, of matching dimension ∣ χ r ∣ |\chi_r| ∣ χ r ∣ , so its cover object is isomorphic to J ′ ( P ) J'(P) J ′ ( P ) ; by Lemma D.3 this identification is unique up to isomorphism. Choosing the Yoneda representative of the r r r -th summand in the construction of Theorem 4.2 to be q ( x r ) q(x_r) q ( x r ) , for a class representative x r x_r x r whose characteristic tuple is the inclusion χ r ⊆ N \chi_r\subseteq\mathbb{N} χ r ⊆ N , and unwinding Algorithm 2 Language equivalence via bisimulation with a generating system
Input: strong nominal automata $A_i = (\Sigma, Q_i, q^i_0, \delta_i, F_i)$ for $i \in \{1,2\}$ over a common alphabet $\Sigma$
Output: whether $L(A_1) = L(A_2)$
$\mathcal{G} \leftarrow \operatorname{create}(Q_1 \sqcup Q_2)$; $\mathcal{G}.\operatorname{merge}(q^1_0,q^2_0)$; enqueue $(q^1_0,q^2_0)$;
while the queue is nonempty do
dequeue $(p_1,p_2)$;
if $(p_1 \in F_1) \ne (p_2 \in F_2)$ then return false;
foreach representative input $a$ of an orbit of $(\mathcal{G}\cdot(p_1,p_2))\times\Sigma$ do
$(p'_1,p'_2) \leftarrow (\delta_1(p_1,a),\delta_2(p_2,a))$;
if not $\mathcal{G}.\operatorname{contains}(p'_1,p'_2)$ then
$\mathcal{G}.\operatorname{merge}(p'_1,p'_2)$;
enqueue $(p'_1,p'_2)$;
return true;
the construction as in the proof of Theorem 4.3, gives p ( h ( x ) ) = [ x ∘ ρ i ] = q ( x ) p(h(x)) = [x \circ\rho_i] = q(x) p ( h ( x )) = [ x ∘ ρ i ] = q ( x ) for every x x x , i.e., p ∘ h = q p \circ h = q p ∘ h = q . Finally, h h h is surjective since every tuple in Inj ( χ r , N ) \operatorname{Inj}(\chi_r,\mathbb{N}) Inj ( χ r , N ) arises as the characteristic tuple of some element of the class.
Operation costs. We detail the worst-case cost for a single call of each operation. The aggregate cost analysis required for the equivalence bound is deferred to the proof of Theorem 5.1.
create ( X ) (X) ( X ) initializes N N N singleton classes with full characteristic sets and identity rays in O ( N ⋅ d ) O(N \cdot d) O ( N ⋅ d ) time.
contains ( x , y ) (x,y) ( x , y ) derives the partial bijection from shared atoms in O ( d ) O(d) O ( d ) time and performs one group-membership test in μ ( d ) \mu(d) μ ( d ) time, for O ( d + μ ( d ) ) O(d+\mu(d)) O ( d + μ ( d )) overall.
merge ( x , y ) (x,y) ( x , y ) executes one branch of Algorithm 1: a class fusion (recomputing the characteristic set via base and all rays of the fused class in O ( N ⋅ d ) O(N \cdot d) O ( N ⋅ d ) , plus a Schreier–Sims rebuild in μ ( d ) \mu(d) μ ( d ) ), a characteristic-set shrink (a base computation and generator restriction, O ( d 2 + μ ( d ) ) O(d^2+\mu(d)) O ( d 2 + μ ( d )) ; rays are restricted lazily upon access), or a generator addition (one rebuild, μ ( d ) \mu(d) μ ( d ) ), for O ( N ⋅ d + d ⋅ μ ( d ) ) O(N \cdot d+d \cdot\mu(d)) O ( N ⋅ d + d ⋅ μ ( d )) worst-case per call. Across any run there are at most N − 1 N-1 N − 1 fusions and at most N ⋅ d N \cdot d N ⋅ d shrinks in total, since each fusion removes a class and each shrink strictly decreases ∑ r ∣ χ r ∣ ≤ N d \sum_r |\chi_r| \le Nd ∑ r ∣ χ r ∣ ≤ N d .
classes extracts the N N N class orbits and sorts their representatives to assign contiguous identifiers, taking O ( N ⋅ d + N log N ) O(N \cdot d+N\log N) O ( N ⋅ d + N log N ) time; this cost enters the quotient operation of Appendix H.1 rather than the equivalence check.
Theorem 5.1 (language equivalence). Let A 1 A_1 A 1 and A 2 A_2 A 2 be strong nominal automata with state spaces Q 1 Q_1 Q 1 and Q 2 Q_2 Q 2 over a common strong alphabet Σ \Sigma Σ , with N = N ( Q 1 ) + N ( Q 2 ) N=N(Q_1)+N(Q_2) N = N ( Q 1 ) + N ( Q 2 ) , d = dim ( Q 1 ⊔ Q 2 ) d=\dim(Q_1\sqcup Q_2) d = dim ( Q 1 ⊔ Q 2 ) , and e = dim ( Σ ) e=\dim(\Sigma) e = dim ( Σ ) . Their language equivalence is decidable in time
O ( N ⋅ d 2 ⋅ N ( Σ ) ⋅ β ( 2 d , e ) ⋅ μ ( d ) + N 2 d ) , O\left(N \cdot d^2 \cdot N(\Sigma) \cdot\beta(2d,e) \cdot\mu(d) + N^2d\right), O ( N ⋅ d 2 ⋅ N ( Σ ) ⋅ β ( 2 d , e ) ⋅ μ ( d ) + N 2 d ) , which, for a fixed alphabet dimension e e e , is polynomial in N N N , N ( Σ ) N(\Sigma) N ( Σ ) , and d d d .
Proof. Due to determinism, language equivalence coincides with bisimilarity. By induction on the search, every enqueued pair is reachable from ( q 0 1 , q 0 2 ) (q^1_0,q^2_0) ( q 0 1 , q 0 2 ) under a common word; hence if Algorithm 2 returns false, some such pair differs in acceptance and the automata are inequivalent. Suppose instead it returns true, and let ∼ \sim ∼ be the final represented relation, which by Invariant 2 of Lemma G.1 is the finest equivariant equivalence relating every merged pair. Let R ⊆ ∼ R \subseteq\sim R ⊆∼ consist of the pairs that agree on acceptance and whose successors on each input are again ∼ \sim ∼ -related; this R R R is an equivariant equivalence containing all merged pairs, since every merged pair is dequeued, its acceptance verified, and its successor orbit representatives merged into ∼ \sim ∼ (guarded by contains). By the minimality of ∼ \sim ∼ we get R = ∼ R = \sim R =∼ , so ∼ \sim ∼ is a bisimulation up to equivariant-equivalence closure; since ( q 0 1 , q 0 2 ) ∈ ∼ (q_0^1, q_0^2) \in\sim ( q 0 1 , q 0 2 ) ∈∼ , the automata are equivalent.
For the time complexity, note that every enqueued pair triggers an effective merge (guarded by contains), and each effective merge performs at least one elementary step (fusion, shrink, or generator addition), so the number of visited pairs is at most the total number of elementary steps, which we now bound. Fusions number at most N − 1 N - 1 N − 1 and shrinks at most N d Nd N d , as each fusion removes a class and each shrink strictly decreases ∑ r ∣ χ r ∣ ≤ N d \sum_r |\chi_r| \le Nd ∑ r ∣ χ r ∣ ≤ N d . Call an epoch of a class a maximal period during which its characteristic set stays fixed; every fusion or shrink ends at most two epochs and starts one, so there are O ( N d ) O(Nd) O ( N d ) epochs overall. Within one epoch the ambient group Sym ( χ r ) \operatorname{Sym}(\chi_r) Sym ( χ r ) is fixed, so the generator additions of that epoch form a strictly increasing chain of subgroups of Sym ( χ r ) \operatorname{Sym}(\chi_r) Sym ( χ r ) , of length O ( ∣ χ r ∣ ) = O ( d ) O(|\chi_r|) = O(d) O ( ∣ χ r ∣ ) = O ( d ) by Babai’s bound on subgroup chains in symmetric groups [2 ] . Hence there are O ( N d ⋅ d ) = O ( N d 2 ) O(Nd \cdot d) = O(Nd^2) O ( N d ⋅ d ) = O ( N d 2 ) elementary steps, and as many visited pairs. Exploring a pair requires iterating over the representative inputs from the orbits of ( G ⋅ ( p 1 , p 2 ) ) × Σ (G \cdot(p_1,p_2)) \times\Sigma ( G ⋅ ( p 1 , p 2 )) × Σ . Since the state pair has dimension at most 2 d 2d 2 d and the alphabet letters have dimension e e e , Proposition 3.5 bounds the number of branches by N ( Σ ) ⋅ β ( 2 d , e ) N(\Sigma) \cdot\beta(2d,e) N ( Σ ) ⋅ β ( 2 d , e ) . Each branch invokes contains, which takes O ( μ ( d ) ) O(\mu(d)) O ( μ ( d )) time for the group membership test. Across all O ( N ⋅ d 2 ) O(N \cdot d^2) O ( N ⋅ d 2 ) visited pairs, this contributes O ( N ⋅ d 2 ⋅ N ( Σ ) ⋅ β ( 2 d , e ) ⋅ μ ( d ) ) O(N \cdot d^2 \cdot N(\Sigma) \cdot\beta(2d,e) \cdot\mu(d)) O ( N ⋅ d 2 ⋅ N ( Σ ) ⋅ β ( 2 d , e ) ⋅ μ ( d )) to the total time. The merges themselves add O ( N 2 d ) O(N^2d) O ( N 2 d ) for ray recomputations across all fusions, O ( N d ⋅ ( d 2 + μ ( d ) ) ) O(Nd \cdot(d^2 + \mu(d))) O ( N d ⋅ ( d 2 + μ ( d ))) for the base computations and generator restrictions of the shrinks, and one Schreier–Sims rebuild per elementary step, O ( N ⋅ d 2 ⋅ μ ( d ) ) O(N \cdot d^2 \cdot\mu(d)) O ( N ⋅ d 2 ⋅ μ ( d )) in total; all of these are absorbed by the contains term and the O ( N 2 d ) O(N^2d) O ( N 2 d ) term. Summing these costs yields the stated time bound. Because β ( 2 d , e ) = O ( ( 2 d ) e e ! ) \beta(2d,e) = O((2d)^e e!) β ( 2 d , e ) = O (( 2 d ) e e !) , the overall time is polynomial in N N N , N ( Σ ) N(\Sigma) N ( Σ ) , and d d d whenever e e e is fixed.
This generalizes the polynomial-time result for register automata [28 ] to strong nominal automata.
Comparison with fresh-register automata. For fresh-register automata, the r r r registers hold pairwise distinct values and each control state fixes which registers are filled (the availability function of [28 Def. 1] ), so the configurations at each control state form a single strong orbit. Hence N = ∣ Q ∣ N = |Q| N = ∣ Q ∣ and d ≤ r d \le r d ≤ r , where ∣ Q ∣ |Q| ∣ Q ∣ is the number of control states and r r r the number of registers.
As we do not treat global freshness, we compare against their h = ∞ h = \infty h = ∞ case, where a conservative bound of O ( ∣ Q ∣ 2 r 2 p ( r ) ) O(|Q|^2r^2p(r)) O ( ∣ Q ∣ 2 r 2 p ( r )) is given [28 ] , with p p p a polynomial accounting for group-theoretic operations; substituting N = ∣ Q ∣ N = |Q| N = ∣ Q ∣ , d ≤ r d \le r d ≤ r , and μ \mu μ for p p p , we write it as O ( N 2 d 2 μ ( d ) ) O(N^2d^2\mu(d)) O ( N 2 d 2 μ ( d )) , which only strengthens their bound. Because their analysis does not charge the cost of updating the generating system, this bound cannot be compared directly with ours; charging each of their O ( N 2 d ) O(N^2d) O ( N 2 d ) updates its worst-case cost of O ( d 2 μ ( d ) ) O(d^2\mu(d)) O ( d 2 μ ( d )) yields O ( N 2 d 3 μ ( d ) ) O(N^2d^3\mu(d)) O ( N 2 d 3 μ ( d )) . At e = 1 e = 1 e = 1 with N ( Σ ) N(\Sigma) N ( Σ ) treated as constant, our bound O ( N d 3 μ ( d ) + N 2 d ) O(Nd^3\mu(d) + N^2d) O ( N d 3 μ ( d ) + N 2 d ) refines this single term into two lower-degree terms and hence is more precise.
Moreover, the comparison does not depend on this recounting, because N N N and d d d are not independent. In a reachable strong nominal automaton, supp ( q 0 ) = ∅ \operatorname{supp}(q_0) = \varnothing supp ( q 0 ) = ∅ and equivariance gives supp ( δ ( q , σ ) ) ⊆ supp ( q ) ∪ supp ( σ ) \operatorname{supp}(\delta(q,\sigma)) \subseteq\operatorname{supp}(q) \cup\operatorname{supp}(\sigma) supp ( δ ( q , σ )) ⊆ supp ( q ) ∪ supp ( σ ) , so each transition adds at most e e e atoms to the
Algorithm 3 Quotient($X, \equiv$)
Input: orbit-finite strong nominal set $X$; equivariant equivalence $\equiv \subseteq X \times X$
Output: strong approximation $P$ of $X/\equiv$ and a lift $h: X \twoheadrightarrow P$
$\mathcal{G} \leftarrow$ create($X$);
foreach orbit $O_1$ of $X$ do
foreach orbit $O_2$ of $X$ not before $O_1$ do
foreach representative pair $(x,y)$ of an orbit of $O_1 \times O_2$ do
if not $\mathcal{G}$.contains$(x,y)$ and $x \equiv y$ then $\mathcal{G}$.merge$(x,y)$;
return $\mathcal{G}$.classes;
support. Furthermore, a shortest run reaching an orbit of maximal dimension visits each orbit at most once, as transporting its suffix along the group action would otherwise shorten it; hence d ≤ e ( N − 1 ) d \le e\,(N-1) d ≤ e ( N − 1 ) . At e = 1 e=1 e = 1 with N ( Σ ) N(\Sigma) N ( Σ ) treated as constant, this yields d < N d<N d < N , so our bound is no larger than even the uncharged O ( N 2 d 2 μ ( d ) ) O(N^2d^2\mu(d)) O ( N 2 d 2 μ ( d )) : indeed N d 3 μ ( d ) ≤ N 2 d 2 μ ( d ) Nd^3\mu(d) \le N^2d^2\mu(d) N d 3 μ ( d ) ≤ N 2 d 2 μ ( d ) and N 2 d ≤ N 2 d 2 μ ( d ) N^2d \le N^2d^2\mu(d) N 2 d ≤ N 2 d 2 μ ( d ) .
Proofs and Pseudocode for Section 5.2
This appendix provides the pseudocode and full proofs for the algorithms of Section 5.2: the quotient operation in Appendix H.1, minimization via Moore’s algorithm in Appendix H.2, and learning via ν L ∗ \nu L^* ν L ∗ in Appendix H.3.
The Quotient Operation
We present the quotient operation as Algorithm 3 and establish its correctness and complexity in Lemma 5.2. It computes the strong approximation of a quotient through the generating system of Appendix G, bypassing any non-strong intermediate structure.
Lemma 5.2 (quotient). Let X X X be an orbit-finite strong nominal set with d = dim ( X ) d=\dim(X) d = dim ( X ) , and let ≡ \equiv ≡ be an equivariant equivalence relation on X X X decidable in time C C C . Then, one can compute the strong approximation P P P of X / ≡ X/\equiv X / ≡ together with a lift h : X ↠ P h:X\twoheadrightarrow P h : X ↠ P of the quotient map q : X → X / ≡ q:X\to X/\equiv q : X → X / ≡ , i.e., an equivariant surjection satisfying p ∘ h = q p\circ h=q p ∘ h = q for the surjection p : P ↠ X / ≡ p:P\twoheadrightarrow X/\equiv p : P ↠ X / ≡ of the strong approximation. This computation runs in time
O ( N ( X ) 2 ⋅ β ( d , d ) ⋅ ( C + μ ( d ) ) ) , O\left(N(X)^2 \cdot\beta(d,d) \cdot(C+\mu(d))\right), O ( N ( X ) 2 ⋅ β ( d , d ) ⋅ ( C + μ ( d )) ) , polynomial in N ( X ) N(X) N ( X ) but, since β ( d , d ) = O ( 2 d d ! ) \beta(d,d)=O(2^{d}d!) β ( d , d ) = O ( 2 d d !) , factorial in d d d .
Proof. Algorithm 3 processes every ≡ \equiv ≡ -related representative pair through G \mathcal{G} G and returns classes. Its correctness follows from Lemma G.1: G \mathcal{G} G maintains the finest equivariant equivalence relation containing the merged pairs, which is ≡ \equiv ≡ itself since ≡ \equiv ≡ is equivariant and all representative pairs are processed, and classes returns the strong approximation of X / ≡ X/\equiv X / ≡ with its lift. Regarding performance, create takes O ( N ( X ) d ) O(N(X)d) O ( N ( X ) d ) time. The nested loops iterate over O ( N ( X ) 2 ) O(N(X)^2) O ( N ( X ) 2 ) orbit pairs, enumerating the β ( d , d ) \beta(d,d) β ( d , d ) orbits of each product as dictated by Proposition 3.5. Processing each such orbit requires one ≡ \equiv ≡ -test, of cost C C C , and at most one contains/merge operation; since μ ( d ) = Ω ( d ) \mu(d)=\Omega(d) μ ( d ) = Ω ( d ) absorbs the O ( d ) O(d) O ( d ) for forming the representative pair and its partial bijection, the non-ray work is O ( C + μ ( d ) ) O(C+\mu(d)) O ( C + μ ( d )) per orbit. The remaining bookkeeping splits into three parts, bounded as in the proof of Theorem 5.1. Ray recomputations are triggered only by class fusions (at most N ( X ) − 1 N(X)-1 N ( X ) − 1 of them) and cost O ( N ( X ) d ) O(N(X)d) O ( N ( X ) d ) per fusion, hence O ( N ( X ) 2 d ) O(N(X)^{2d}) O ( N ( X ) 2 d ) in total. Characteristic-set shrinks number at most N ( X ) d N(X)d N ( X ) d and cost O ( d 2 + μ ( d ) ) O(d^2+\mu(d)) O ( d 2 + μ ( d )) each (a base computation and generator restriction). Generator additions form subgroup chains of length O ( d ) O(d) O ( d ) per epoch [2 ] , for O ( N ( X ) d 2 ) O(N(X)d^2) O ( N ( X ) d 2 ) elementary steps and as many Schreier–Sims rebuilds, contributing O ( N ( X ) d 2 ⋅ μ ( d ) ) O(N(X)d^2\cdot\mu(d)) O ( N ( X ) d 2 ⋅ μ ( d )) in total. All three terms are dominated by the per-pattern work because d 3 ≤ N ( X ) β ( d , d ) μ ( d ) d^3\le N(X)\,\beta(d,d)\,\mu(d) d 3 ≤ N ( X ) β ( d , d ) μ ( d ) holds for all N ( X ) ≥ 1 N(X)\ge1 N ( X ) ≥ 1 and d ≥ 1 d\ge1 d ≥ 1 (as β ( d , d ) ≥ d 2 \beta(d,d)\ge d^2 β ( d , d ) ≥ d 2 and μ ( d ) = Ω ( d ) \mu(d)=\Omega(d) μ ( d ) = Ω ( d ) ), and are thus absorbed into the bound. This yields a dominant total time of O ( N ( X ) 2 β ( d , d ) ( C + μ ( d ) ) + N ( X ) 2 d + N ( X ) d 2 ⋅ μ ( d ) ) = O ( N ( X ) 2 β ( d , d ) ( C + μ ( d ) ) ) O(N(X)^2\beta(d,d)(C+\mu(d))+N(X)^2d+N(X)d^2\cdot\mu(d))=O(N(X)^2\beta(d,d)(C+\mu(d))) O ( N ( X ) 2 β ( d , d ) ( C + μ ( d )) + N ( X ) 2 d + N ( X ) d 2 ⋅ μ ( d )) = O ( N ( X ) 2 β ( d , d ) ( C + μ ( d ))) . Given β ( d , d ) = O ( 2 d d ! ) \beta(d,d)=O(2^d d!) β ( d , d ) = O ( 2 d d !) , this bound is polynomial in N ( X ) N(X) N ( X ) but factorially dependent on d d d .
The generating system is not strictly required for the quotient operation. A support-intersection variant enumerates the β ( d , d ) \beta(d,d) β ( d , d ) partial bijections per orbit pair and tests ≡ \equiv ≡ on a representative pair of each product orbit directly. The least support of an ≡ \equiv ≡ -class equals the intersection of the supports of its members: the inclusion into each member’s support is immediate from equivariance of the quotient map, and conversely, if a ∉ supp ( [ x ] ≡ ) a\notin\operatorname{supp}([x]_{\equiv}) a ∈ / supp ([ x ] ≡ ) , swapping a a a with a fresh atom fixes the class and produces a member whose support avoids a a a . Intersecting the supports of the equivalent representatives incrementally along this enumeration therefore yields the strong approximation together with its lift. This replaces the μ ( d ) \mu(d) μ ( d ) factor of Lemma 5.2 by the O ( d ) O(d) O ( d ) cost of the support intersections, for a total of O ( N ( X ) 2 β ( d , d ) ( C + d ) ) O(N(X)^2\beta(d,d)(C+d)) O ( N ( X ) 2 β ( d , d ) ( C + d )) .
The substitution extends to Theorems 5.3 and 5.4, whose μ ( d ) \mu(d) μ ( d ) factors are, in principle, not essential either. For learning, each ∼ r o w \sim_{\mathrm{row}} ∼ row -test reads the observation table directly, so the hypothesis construction can use the support-intersection variant as is. For minimization, one instead iterates at the level of sets, as in Moore’s algorithm for Ord [40 Sec. 3.1] : maintain ≡ k \equiv_k ≡ k as an equivariant subset of Q × Q Q\times Q Q × Q and compute ≡ k + 1 \equiv_{k+1} ≡ k + 1 from it by the effective operations of Appendix F (a product ≡ k × Σ \equiv_k\times\Sigma ≡ k × Σ , a filter selecting the orbits whose successor pair leaves ≡ k \equiv_k ≡ k , an image under the projection, and a set difference), each O ( 1 ) O(1) O ( 1 ) per orbit, and extract the strong approximation by a single support-intersection quotient after stabilization. Each round then costs O ( N ( Q ) 2 β ( d , d ) N ( Σ ) β ( 2 d , e ) ) O(N(Q)^2\beta(d,d)N(\Sigma)\beta(2d,e)) O ( N ( Q ) 2 β ( d , d ) N ( Σ ) β ( 2 d , e )) , removing the μ ( d ) \mu(d) μ ( d ) factor from Theorem 5.3. In practice, however, the generating system stores the same relation far more compactly (generators instead of up to β ( d , d ) \beta(d,d) β ( d , d ) patterns per orbit pair), and G . c o n t a i n s \mathcal{G}.\mathrm{contains} G . contains skips the ≡ \equiv ≡ -test for pairs already known to be equivalent, which is beneficial when C C C dominates, as in minimization, where each ≡ k + 1 \equiv_{k+1} ≡ k + 1 -test iterates over N ( Σ ) ⋅ β ( 2 d , e ) N(\Sigma)\cdot\beta(2d,e) N ( Σ ) ⋅ β ( 2 d , e ) representative inputs.
Minimization
We present minimization as Algorithm 4 and analyze its complexity in Theorem 5.3. The input automaton is assumed reachable; the reachable part can be precomputed by a breadth-first exploration of orbits as in Algorithm 2. It is Moore’s algorithm: it computes the k k k -step Myhill–Nerode relations ≡ k \equiv_k ≡ k until they stabilize, computing the strong approximation of each successive quotient with Algorithm 3. We retain the generating system G k \mathcal{G}_k G k built by the k k k -th call to Quotient across rounds, so that each query q ≡ k q ′ q\equiv_k q' q ≡ k q ′ is answered by G k . c o n t a i n s \mathcal{G}_k.\mathrm{contains} G k . contains in O ( d + μ ( d ) ) O(d+\mu(d)) O ( d + μ ( d )) time. Our implementation additionally restricts the enumeration in each round to pairs within a common ≡ k \equiv_k ≡ k -class and memoizes falsified pairs across rounds; both optimizations are sound because the relations ≡ k \equiv_k ≡ k only refine, and they do not affect the worst-case bound.
The stabilization test in the loop condition needs care: the class count N ( P k ) N(P_k) N ( P k ) alone cannot detect a refinement that only grows the least support of a class or shrinks its local symmetry group, and stopping on the count alone may freeze a relation that is not yet a Algorithm 4 Minimize(A \mathcal{A} A ) via Moore’s algorithm
Input: reachable strong nominal automaton A = ( Σ , Q , q 0 , δ , F ) \mathcal{A} = (\Sigma, Q, q_0, \delta, F) A = ( Σ , Q , q 0 , δ , F )
Output: strong nominal automaton A ′ \mathcal{A}' A ′ , a strong lift of the minimal automaton of A \mathcal{A} A
( P 0 , h 0 ) ← Quotient ( Q , ≡ 0 ) (P_0, h_0) \leftarrow\operatorname{Quotient}(Q, \mathrel{\equiv_0}) ( P 0 , h 0 ) ← Quotient ( Q , ≡ 0 ) , where q ≡ 0 q ′ ⟺ ( q ∈ F ⟺ q ′ ∈ F ) q \mathrel{\equiv_0} q' \Longleftrightarrow(q \in F \Longleftrightarrow q' \in F) q ≡ 0 q ′ ⟺ ( q ∈ F ⟺ q ′ ∈ F ) ;
k ← 0 k \leftarrow0 k ← 0 ;
repeat
( P k + 1 , h k + 1 ) ← Quotient ( Q , ≡ k + 1 ) \quad(P_{k+1}, h_{k+1}) \leftarrow\operatorname{Quotient}(Q, \mathrel{\equiv_{k+1}}) ( P k + 1 , h k + 1 ) ← Quotient ( Q , ≡ k + 1 ) , where
q ≡ k + 1 q ′ ⟺ ( q ≡ k q ′ and ∀ a ∈ Σ , δ ( q , a ) ≡ k δ ( q ′ , a ) ) \quad q \mathrel{\equiv_{k+1}} q' \Longleftrightarrow(q \mathrel{\equiv_k} q' \text{ and } \forall a \in\Sigma,\ \delta(q,a) \mathrel{\equiv_k} \delta(q',a)) q ≡ k + 1 q ′ ⟺ ( q ≡ k q ′ and ∀ a ∈ Σ , δ ( q , a ) ≡ k δ ( q ′ , a )) ;
k ← k + 1 \quad k \leftarrow k+1 k ← k + 1 ;
until ≡ k = ≡ k − 1 \mathrel{\equiv_k} = \mathrel{\equiv_{k-1}} ≡ k = ≡ k − 1 ;
return the strong nominal automaton on P k P_k P k induced by h k h_k h k via Theorem 4.4;
congruence. The following lemma shows that these three quantities together witness every refinement.
Lemma H.1 (refinement measure). Let ≡ ′ ⊆ ≡ \mathrel{\equiv'} \subseteq\mathrel{\equiv} ≡ ′ ⊆ ≡ be equivariant equivalence relations on an orbit-finite nominal set X X X . If ≡ ′ ≠ ≡ \mathrel{\equiv'} \ne\mathrel{\equiv} ≡ ′ = ≡ , then N ( X / ≡ ′ ) > N ( X / ≡ ) N(X/\mathrel{\equiv'}) > N(X/\mathrel{\equiv}) N ( X / ≡ ′ ) > N ( X / ≡ ) , or some ≡ ′ \mathrel{\equiv'} ≡ ′ -class has a strictly larger least support, or a strictly smaller local symmetry group, than the ≡ \mathrel{\equiv} ≡ -class containing it.
Proof. The map X / ≡ ′ → X / ≡ X/\mathrel{\equiv'} \to X/\mathrel{\equiv} X / ≡ ′ → X / ≡ , [ x ] ≡ ′ ↦ [ x ] ≡ [x]_{\mathrel{\equiv'}} \mapsto[x]_{\mathrel{\equiv}} [ x ] ≡ ′ ↦ [ x ] ≡ , is an equivariant surjection, so N ( X / ≡ ′ ) ≥ N ( X / ≡ ) N(X/\mathrel{\equiv'}) \ge N(X/\mathrel{\equiv}) N ( X / ≡ ′ ) ≥ N ( X / ≡ ) ; moreover, for classes C ′ ⊆ C C' \subseteq C C ′ ⊆ C we have supp ( C ) ⊆ supp ( C ′ ) \operatorname{supp}(C) \subseteq\operatorname{supp}(C') supp ( C ) ⊆ supp ( C ′ ) , and Stab G ( C ′ ) ⊆ Stab G ( C ) \operatorname{Stab}_G(C') \subseteq\operatorname{Stab}_G(C) Stab G ( C ′ ) ⊆ Stab G ( C ) , since g ⋅ C ′ = C ′ g \cdot C' = C' g ⋅ C ′ = C ′ makes g ⋅ C g \cdot C g ⋅ C (a class of the equivariant relation ≡ \mathrel{\equiv} ≡ ) meet C C C , forcing g ⋅ C = C g \cdot C = C g ⋅ C = C . Now assume all three quantities are preserved. First, supp ( C ′ ) = supp ( C ) \operatorname{supp}(C') = \operatorname{supp}(C) supp ( C ′ ) = supp ( C ) together with equal local symmetry groups gives Stab G ( C ′ ) = Stab G ( C ) \operatorname{Stab}_G(C') = \operatorname{Stab}_G(C) Stab G ( C ′ ) = Stab G ( C ) : for g ∈ Stab G ( C ) g \in\operatorname{Stab}_G(C) g ∈ Stab G ( C ) , pick g ′ ∈ Stab G ( C ′ ) g' \in\operatorname{Stab}_G(C') g ′ ∈ Stab G ( C ′ ) with g ′ ∣ supp ( C ′ ) = g ∣ supp ( C ) g'|_{\operatorname{supp}(C')} = g|_{\operatorname{supp}(C)} g ′ ∣ supp ( C ′ ) = g ∣ supp ( C ) , possible as the local symmetries coincide; then g ′ − 1 g ∈ Fix G ( supp ( C ′ ) ) ⊆ Stab G ( C ′ ) g'^{-1}g \in\operatorname{Fix}_G(\operatorname{supp}(C')) \subseteq\operatorname{Stab}_G(C') g ′ − 1 g ∈ Fix G ( supp ( C ′ )) ⊆ Stab G ( C ′ ) , so g ∈ Stab G ( C ′ ) g \in\operatorname{Stab}_G(C') g ∈ Stab G ( C ′ ) . Next, fix an ≡ \mathrel{\equiv} ≡ -class C C C and ≡ ′ \mathrel{\equiv'} ≡ ′ -subclasses C ′ , C ′ ′ ⊆ C C', C'' \subseteq C C ′ , C ′′ ⊆ C . Since N ( X / ≡ ′ ) = N ( X / ≡ ) N(X/\mathrel{\equiv'}) = N(X/\mathrel{\equiv}) N ( X / ≡ ′ ) = N ( X / ≡ ) , the orbit map induced by the surjection above is a bijection, so C ′ ′ C'' C ′′ and C ′ C' C ′ lie in a common orbit: C ′ ′ = g ⋅ C ′ C'' = g \cdot C' C ′′ = g ⋅ C ′ for some g ∈ G g \in G g ∈ G . Then g ⋅ C ′ ⊆ C ∩ g ⋅ C g \cdot C' \subseteq C \cap g \cdot C g ⋅ C ′ ⊆ C ∩ g ⋅ C forces g ⋅ C = C g \cdot C = C g ⋅ C = C , so g ∈ Stab G ( C ) g \in\operatorname{Stab}_G(C) g ∈ Stab G ( C ) and, by the first step, g ∈ Stab G ( C ′ ) g \in\operatorname{Stab}_G(C') g ∈ Stab G ( C ′ ) ; hence C ′ ′ = g ⋅ C ′ = C ′ C'' = g \cdot C' = C' C ′′ = g ⋅ C ′ = C ′ . Thus every ≡ \mathrel{\equiv} ≡ -class is a single ≡ ′ \mathrel{\equiv'} ≡ ′ -class, i.e., ≡ ′ = ≡ \mathrel{\equiv'} = \mathrel{\equiv} ≡ ′ = ≡ .
This three-part measure mirrors the convergence argument for minimizing history-dependent automata [14 Thm. 2] , where each iteration either splits a block, adds a name, or shrinks a symmetry group.
Theorem 5.3 (minimization). Let A \mathcal{A} A be a reachable strong nominal automaton over a strong alphabet Σ \Sigma Σ , with N ( Q ) N(Q) N ( Q ) state orbits, d = dim ( Q ) d = \dim(Q) d = dim ( Q ) , and e = dim ( Σ ) e = \dim(\Sigma) e = dim ( Σ ) . Moore’s algorithm computes a strong lift of the minimal automaton of L ( A ) L(\mathcal{A}) L ( A ) in time
O ( N ( Q ) 3 ⋅ d ⋅ β ( d , d ) ⋅ N ( Σ ) β ( 2 d , e ) ⋅ μ ( d ) ) O\left(N(Q)^3 \cdot d \cdot\beta(d,d) \cdot N(\Sigma)\beta(2d,e) \cdot\mu(d)\right) O ( N ( Q ) 3 ⋅ d ⋅ β ( d , d ) ⋅ N ( Σ ) β ( 2 d , e ) ⋅ μ ( d ) ) which, for a fixed e e e , is polynomial in N ( Q ) N(Q) N ( Q ) and N ( Σ ) N(\Sigma) N ( Σ ) but factorial in d d d .
Proof. By induction, ≡ k \mathrel{\equiv_k} ≡ k relates exactly the states that agree on acceptance after every word of length at most k k k ; the relations refine monotonically, and once ≡ k = ≡ k − 1 \mathrel{\equiv_k} = \mathrel{\equiv_{k-1}} ≡ k = ≡ k − 1 the relation is closed under transitions, hence it is the Myhill–Nerode equivalence of A \mathcal{A} A ; since A \mathcal{A} A is reachable, Q / ≡ k Q/\mathrel{\equiv_k} Q / ≡ k is the state space of the minimal automaton. The strong approximation P k P_k P k of Q / ≡ k Q/\mathrel{\equiv_k} Q / ≡ k then serves as the state space of a strong lift of the minimal automaton per Corollary 4.5; the result A ′ \mathcal{A}' A ′ is this lift, with the transition function lifted onto P k P_k P k by Theorem 4.4. The lift is polynomial in the input and absorbed into the bound below. For the number of rounds, each round with ≡ k + 1 ≠ ≡ k \equiv_{k+1} \ne\equiv_k ≡ k + 1 = ≡ k advances the measure of Lemma H.1 : it increases the class-orbit count (at most N ( Q ) N(Q) N ( Q ) times in total, since a quotient of Q Q Q has at most N ( Q ) N(Q) N ( Q ) orbits), grows the least support of some class orbit (at most d d d times each), or strictly shrinks the local symmetry group of some class orbit (at most O ( d ) O(d) O ( d ) times each, since a strictly descending chain of subgroups of S d S_d S d has length O ( d ) O(d) O ( d ) ) [2 ] . Hence the loop runs O ( N ( Q ) ⋅ d ) O(N(Q) \cdot d) O ( N ( Q ) ⋅ d ) times. The generating system maintains exactly these three quantities (the classes, their characteristic sets, and their local symmetry groups), so by Lemma H.1 the stabilization test ≡ k = ≡ k − 1 \equiv_k = \equiv_{k-1} ≡ k = ≡ k − 1 amounts to comparing them across consecutive rounds, in time absorbed by the round itself.
Deciding ≡ k + 1 \equiv_{k+1} ≡ k + 1 for a state pair, the conjunct q ≡ k q ′ q \equiv_k q' q ≡ k q ′ is one contains query on G k \mathcal{G}_k G k , and the universal quantification over Σ \Sigma Σ is sound to decide on one representative input per orbit of ( G ⋅ ( q , q ′ ) ) × Σ (G \cdot(q,q')) \times\Sigma ( G ⋅ ( q , q ′ )) × Σ by equivariance, as in Algorithm 2. The state pair has dimension at most 2 d 2d 2 d , so Proposition 3.5 bounds the number of branches by N ( Σ ) β ( 2 d , e ) N(\Sigma)\,\beta(2d,e) N ( Σ ) β ( 2 d , e ) , each performing one contains query in O ( d + μ ( d ) ) = O ( μ ( d ) ) O(d+\mu(d)) = O(\mu(d)) O ( d + μ ( d )) = O ( μ ( d )) ; thus ≡ k + 1 \equiv_{k+1} ≡ k + 1 is decidable in C = O ( N ( Σ ) β ( 2 d , e ) μ ( d ) ) C = O(N(\Sigma)\,\beta(2d,e)\,\mu(d)) C = O ( N ( Σ ) β ( 2 d , e ) μ ( d )) . Each round is a call Quotient( Q , ≡ k + 1 ) (Q,\equiv_{k+1}) ( Q , ≡ k + 1 ) , costing O ( N ( Q ) 2 β ( d , d ) ( C + μ ( d ) ) ) O(N(Q)^2\beta(d,d)(C+\mu(d))) O ( N ( Q ) 2 β ( d , d ) ( C + μ ( d ))) by Lemma 5.2; multiplying by the O ( N ( Q ) ⋅ d ) O(N(Q)\cdot d) O ( N ( Q ) ⋅ d ) rounds gives the stated bound. ◀
Our result is the Eq counterpart of the Ord minimization bound of [40 Thm. 8.2] , which is O ( 3 5 k ⋅ k ⋅ N ( Q ) 3 N ( Σ ) ) O(3^{5k}\cdot k\cdot N(Q)^{3}N(\Sigma)) O ( 3 5 k ⋅ k ⋅ N ( Q ) 3 N ( Σ )) where k = dim ( Q ⊔ Σ ) k = \dim(Q\sqcup\Sigma) k = dim ( Q ⊔ Σ ) : a product of single Ord-orbits of dimensions m m m and n n n has β O r d ( m , n ) = O ( 3 m + n ) \beta_{\mathrm{Ord}}(m,n) = O(3^{m+n}) β Ord ( m , n ) = O ( 3 m + n ) orbits [40 Thm. 8.1] , so substituting β O r d \beta_{\mathrm{Ord}} β Ord for β \beta β in our bound, which depends on the symmetry only through this product-orbit count, yields O ( N ( Q ) 3 ⋅ d ⋅ N ( Σ ) ⋅ 3 4 d + e ⋅ μ ( d ) ) O(N(Q)^3\cdot d\cdot N(\Sigma)\cdot3^{4d+e}\cdot\mu(d)) O ( N ( Q ) 3 ⋅ d ⋅ N ( Σ ) ⋅ 3 4 d + e ⋅ μ ( d )) , which recovers theirs up to the μ ( d ) \mu(d) μ ( d ) factor, as d ≤ k d \le k d ≤ k and 4 d + e ≤ 5 k 4d+e \le5k 4 d + e ≤ 5 k . The remaining μ ( d ) \mu(d) μ ( d ) factor stems from the generating system and is not essential: the set-level iteration of Appendix § 16 .§ 1 , with a single final support-intersection quotient, avoids it entirely, yielding O ( N ( Q ) 3 ⋅ d ⋅ N ( Σ ) ⋅ 3 4 d + e ) O(N(Q)^3\cdot d\cdot N(\Sigma)\cdot3^{4d+e}) O ( N ( Q ) 3 ⋅ d ⋅ N ( Σ ) ⋅ 3 4 d + e ) after the substitution, which is subsumed by their bound.
The L Algorithm
We instantiate the nominal ν L ∗ \nu L^* ν L ∗ algorithm [24 ] , the nominal generalization of Angluin’s L ∗ L^* L ∗ [1 ] , to strong nominal alphabets, replacing their implicit quotient of the prefix set by the strong approximation of Lemma 5.2. The control flow (closedness, consistency, and counterexample handling) matches the standard ν L ∗ \nu L^* ν L ∗ ; the only structural change is that hypothesis construction goes through Quotient, yielding a strong nominal automaton via Theorem 4.4 rather than a quotient in N o m \mathsf{Nom} Nom .
Membership and equivalence queries. The learner interacts with a teacher through two oracles. A membership query MQ ( w ) \operatorname{MQ}(w) MQ ( w ) reports whether a word w ∈ Σ ∗ w \in\Sigma^* w ∈ Σ ∗ belongs to the target language L L L , and an equivalence query EQ ( H ) \operatorname{EQ}(\mathcal{H}) EQ ( H ) returns 1 1 1 if the hypothesis automaton H \mathcal{H} H recognizes L L L , or otherwise a counterexample in the symmetric difference L ( H ) △ L L(\mathcal{H}) \triangle L L ( H ) △ L . Since L L L is equivariant, both oracles are equivariant (MQ ( g ⋅ w ) = MQ ( w ) \operatorname{MQ}(g \cdot w) = \operatorname{MQ}(w) MQ ( g ⋅ w ) = MQ ( w ) , and EQ may be answered up to the G G G -action), so the learner only needs to query orbit representatives, which keeps the table orbit-finite. In our experiments, these oracles are realized black-box across a process boundary, as detailed in Appendix § 17 .§ 3 .
Observation table. The basic data structure is an observation table ( S , E , T ) (S,E,T) ( S , E , T ) . Here S S S and E E E are equivariant orbit-finite subsets of Σ ∗ \Sigma^* Σ ∗ , where S S S is prefix-closed and E E E is suffix-closed, and T : ( S ∪ S ⋅ Σ ) × E → { 0 , 1 } T:(S\cup S\cdot\Sigma)\times E \to\{0,1\} T : ( S ∪ S ⋅ Σ ) × E → { 0 , 1 } is the equivariant map defined by T ( s , e ) = 1 T(s,e)=1 T ( s , e ) = 1 iff s ∈ L s\in L s ∈ L . We write row ( u ) : e ↦ T ( u , e ) \operatorname{row}(u):e\mapsto T(u,e) row ( u ) : e ↦ T ( u , e ) for the curried counterpart of T T T , and u ∼ r o w v u\mathrel{\sim_{\mathrm{row}}}v u ∼ row v for the row-equivalence Algorithm 5 MakeHypothesis( S , E , T ) (S, E, T) ( S , E , T )
Input: closed and consistent observation table ( S , E , T ) (S, E, T) ( S , E , T ) Output: strong nominal automaton H \mathcal{H} H consistent with the table ( P , h ) ← Quotient ( S ∪ S ⋅ Σ , ∼ r o w ) ; (P, h) \leftarrow\operatorname{Quotient}(S \cup S \cdot\Sigma, \sim_{\mathrm{row}}); ( P , h ) ← Quotient ( S ∪ S ⋅ Σ , ∼ row ) ; q 0 ← h ( ϵ ) ; q_0 \leftarrow h(\epsilon); q 0 ← h ( ϵ ) ; F ← { h ( s ) ∣ s ∈ S , row ( s ) ( ϵ ) = 1 } ; F \leftarrow\{h(s) \mid s \in S,\ \operatorname{row}(s)(\epsilon) = 1\}; F ← { h ( s ) ∣ s ∈ S , row ( s ) ( ϵ ) = 1 } ; δ ( h ( s ) , a ) ← h ( s ⋅ a ) \delta(h(s), a) \leftarrow h(s \cdot a) δ ( h ( s ) , a ) ← h ( s ⋅ a ) for one representative ( s , a ) (s,a) ( s , a ) per orbit of h ( S ) × Σ h(S) \times\Sigma h ( S ) × Σ , extended equivariantly; return ( Σ , P , q 0 , δ , F ) ; (\Sigma, P, q_0, \delta, F); ( Σ , P , q 0 , δ , F ) ;
relation row ( u ) = row ( v ) \operatorname{row}(u) = \operatorname{row}(v) row ( u ) = row ( v ) . By [24 Lem. 1] , ∼ r o w \sim_{\mathrm{row}} ∼ row is an equivariant equivalence relation refined by ≡ L \equiv_L ≡ L (that is, u ≡ L v ⇒ u ∼ r o w v u \equiv_L v \Rightarrow u \sim_{\mathrm{row}} v u ≡ L v ⇒ u ∼ row v ). The table admits a finite representation: each orbit of S S S , E E E , S ⋅ Σ S \cdot\Sigma S ⋅ Σ has a canonical representative, and each cell T i j : G ⋅ s i × G ⋅ e j → { 0 , 1 } T_{ij}: G \cdot s_i \times G \cdot e_j \to\{0,1\} T ij : G ⋅ s i × G ⋅ e j → { 0 , 1 } is orbit-finite, hence fillable with finitely many membership queries even though the underlying product orbit may split, as shown in Proposition 3.5 .
Closedness and consistency. The table is closed if for every t ∈ S ⋅ Σ t \in S \cdot\Sigma t ∈ S ⋅ Σ there is s ∈ S s \in S s ∈ S with t ∼ r o w s t \sim_{\mathrm{row}} s t ∼ row s , and consistent if s 1 ∼ r o w s 2 s_1 \sim_{\mathrm{row}} s_2 s 1 ∼ row s 2 implies s 1 a ∼ r o w s 2 a s_1 a \sim_{\mathrm{row}} s_2 a s 1 a ∼ row s 2 a for every s 1 , s 2 ∈ S s_1, s_2 \in S s 1 , s 2 ∈ S and a ∈ Σ a \in\Sigma a ∈ Σ . Both conditions are decidable thanks to orbit-finiteness and equivariance. For closedness, it suffices to iterate over orbit-representatives t ∈ S ⋅ Σ t \in S \cdot\Sigma t ∈ S ⋅ Σ and s ∈ S s \in S s ∈ S together with the finitely many support-level partial bijections π \pi π between supp ( s ) \operatorname{supp}(s) supp ( s ) and supp ( t ) \operatorname{supp}(t) supp ( t ) ; the condition t ∼ r o w s t \sim_{\mathrm{row}} s t ∼ row s holds iff some such π \pi π satisfies row ( t ) = π ⋅ row ( s ) \operatorname{row}(t) = \pi\cdot\operatorname{row}(s) row ( t ) = π ⋅ row ( s ) . For consistency, the set of inconsistencies
{ ( s 1 , s 2 , a , e ) ∈ S × S × Σ × E ∣ s 1 ∼ r o w s 2 ∧ row ( s 1 a e ) ≠ row ( s 2 a e ) } \{(s_1,s_2,a,e) \in S \times S \times\Sigma\times E \mid s_1 \sim_{\mathrm{row}} s_2 \land\operatorname{row}(s_1ae) \ne\operatorname{row}(s_2ae)\} {( s 1 , s 2 , a , e ) ∈ S × S × Σ × E ∣ s 1 ∼ row s 2 ∧ row ( s 1 a e ) = row ( s 2 a e )}
is an equivariant subset of an orbit-finite set and hence orbit-finite; deciding its emptiness over orbit-representatives yields, when non-empty, a witness ( s 1 , s 2 , a , e ) (s_1,s_2,a,e) ( s 1 , s 2 , a , e ) whose separator a e ae a e is added to E E E .
Hypothesis construction. When the table is closed and consistent, we extract a strong nominal automaton by quotienting S ∪ S ⋅ Σ S \cup S \cdot\Sigma S ∪ S ⋅ Σ by ∼ r o w \sim_{\mathrm{row}} ∼ row via Algorithm 3. The strong approximation P P P of ( S ∪ S ⋅ Σ ) / ∼ r o w (S \cup S \cdot\Sigma)/{\sim_{\mathrm{row}}} ( S ∪ S ⋅ Σ ) / ∼ row returned by Quotient serves as the state space; by Theorem 4.3 and closedness, P P P inherits the orbit structure of S / ∼ r o w S/{\sim_{\mathrm{row}}} S / ∼ row . The transition function is defined on one representative ( h ( s ) , a ) (h(s),a) ( h ( s ) , a ) per orbit of P × Σ P \times\Sigma P × Σ with s ∈ S s \in S s ∈ S (closedness lets every state of P P P be so represented) and extended equivariantly; consistency makes the quotient-level transition [ s ] ∼ r o w ↦ [ s ⋅ a ] ∼ r o w [s]_{\sim_{\mathrm{row}}} \mapsto[s \cdot a]_{\sim_{\mathrm{row}}} [ s ] ∼ row ↦ [ s ⋅ a ] ∼ row well-defined, and our assignment lifts it along p ∘ h = q p \circ h = q p ∘ h = q , as in Theorem 4.4. The equivariant extension is well-defined: any π ∈ G \pi\in G π ∈ G stabilizing ( h ( s ) , a ) (h(s),a) ( h ( s ) , a ) fixes the atoms of h ( s ) h(s) h ( s ) , i.e., supp ( row ( s ) ) \operatorname{supp}(\operatorname{row}(s)) supp ( row ( s )) , and, Σ \Sigma Σ being strong, supp ( a ) \operatorname{supp}(a) supp ( a ) pointwise; then π ⋅ s ∼ r o w s \pi\cdot s \sim_{\mathrm{row}} s π ⋅ s ∼ row s , so consistency gives row ( π ⋅ ( s ⋅ a ) ) = row ( s ⋅ a ) \operatorname{row}(\pi\cdot(s \cdot a)) = \operatorname{row}(s \cdot a) row ( π ⋅ ( s ⋅ a )) = row ( s ⋅ a ) , whence supp ( row ( s ⋅ a ) ) ⊆ supp ( row ( s ) ) ∪ supp ( a ) \operatorname{supp}(\operatorname{row}(s \cdot a)) \subseteq\operatorname{supp}(\operatorname{row}(s)) \cup\operatorname{supp}(a) supp ( row ( s ⋅ a )) ⊆ supp ( row ( s )) ∪ supp ( a ) and π \pi π fixes the characteristic tuple h ( s ⋅ a ) h(s \cdot a) h ( s ⋅ a ) .
Counterexample handling. Algorithm 6 processes counterexamples by adding their suffixes to E E E rather than their prefixes to S S S . This distinguishing-suffix variant is explicitly sanctioned by [24 Sec. 4.1] : their termination argument is insensitive to whether counterexamples are handled by row extension or column extension, so any strategy that yields a strictly refined hypothesis is admissible. Our implementation simply adds all suffixes of c e x cex ce x as columns [22 ] , shortest first, a column-based handling also adopted for Ord [40 ] . As [24 ] observe, a finer analysis of counterexamples in the style of Rivest and Schapire [35 ] , adding fewer columns, could be substituted as an optimization; we do not pursue it.
Algorithm 6 ν L ∗ \nu L^* ν L ∗ via distinguishing-suffix counterexamples
Input: teacher with membership query MQ and equivalence query EQ over a strong alphabet Σ \Sigma Σ
Output: strong nominal automaton recognizing the target language
S ← { ϵ } S \leftarrow\{\epsilon\} S ← { ϵ } ; E ← { ϵ } E \leftarrow\{\epsilon\} E ← { ϵ } ; fill T T T over ( S ∪ S ⋅ Σ ) × E (S \cup S \cdot\Sigma) \times E ( S ∪ S ⋅ Σ ) × E via MQ;
while true do
if the table is not closed then
promote a witness t ∈ S ⋅ Σ t \in S \cdot\Sigma t ∈ S ⋅ Σ to S S S ;
extend S ⋅ Σ S \cdot\Sigma S ⋅ Σ , refill, and continue
if the table is not consistent then
add the witness separator a e a e a e to E E E ;
refill, and continue
H ← MakeHypothesis ( S , E , T ) \mathcal{H} \leftarrow\operatorname{MakeHypothesis}(S,E,T) H ← MakeHypothesis ( S , E , T ) ;
c e x ← EQ ( H ) cex \leftarrow\operatorname{EQ}(\mathcal{H}) ce x ← EQ ( H ) ;
if c e x = ⊥ cex = \bot ce x = ⊥ then return H \mathcal{H} H ;
foreach suffix w w w of c e x cex ce x , shortest first do
E ← E ∪ G ⋅ w E \leftarrow E \cup G \cdot w E ← E ∪ G ⋅ w ; refill T T T over ( S ∪ S ⋅ Σ ) × G ⋅ w (S \cup S \cdot\Sigma) \times G \cdot w ( S ∪ S ⋅ Σ ) × G ⋅ w ;
Theorem 5.4 (learning). Let A min A_{\min} A m i n be the minimal nominal automaton of an equivariant language, with n n n state orbits, state dimension d d d , and strong alphabet Σ \Sigma Σ of dimension e = dim ( Σ ) e = \dim(\Sigma) e = dim ( Σ ) ; let m m m be the length of the longest counterexample and ℓ \ell ℓ the maximum column length of the observation table (the proof shows ℓ = m + O ( n d ) \ell= m + O(nd) ℓ = m + O ( n d ) ). Then, ν L ∗ \nu L^* ν L ∗ learns a strong lift of A min A_{\min} A m i n using O ( n d ) O(nd) O ( n d ) equivalence queries and
O ( n 2 d ⋅ ( m + 1 ) ⋅ N ( Σ ) ⋅ β ( e n , e ) ⋅ β ( e n , e ℓ ) ) O\left(n^2 d \cdot(m+1) \cdot N(\Sigma) \cdot\beta(en,e) \cdot\beta(en,e\ell)\right) O ( n 2 d ⋅ ( m + 1 ) ⋅ N ( Σ ) ⋅ β ( e n , e ) ⋅ β ( e n , e ℓ ) ) membership queries. Each hypothesis is constructed by Lemma 5.2 in time factorial in the observation dimensions, at most e n en e n (rows) and e ℓ e\ell e ℓ (columns).
Proof. We first note what is learned, then argue termination, then bound the query complexity, and finally discuss the per-hypothesis runtime. The argument parallels [24 Thm. 2] , with their splitting function f A f_A f A instantiated to our β \beta β ; since our variant handles counterexamples by columns rather than rows, the row and column bounds below are rebalanced accordingly.
Correctness. As in [24 Thm. 2] , at termination the closed and consistent table yields the minimal automaton: S / ∼ r o w S/{\sim_{\mathrm{row}}} S / ∼ row has exactly the n n n orbits and the dimensions of the state space of A min A_{\min} A m i n . Since Algorithm 5 constructs the final hypothesis as the strong approximation of S / ∼ r o w S/{\sim_{\mathrm{row}}} S / ∼ row through Quotient, as in Lemma 5.2 and Theorem 4.4, the learned automaton is a strong lift of A min A_{\min} A m i n , as stated in Corollary 4.5.
Termination. The three monotone parameters of [24 Thm. 2] control the outer loop:
Orbit count of S / ∼ r o w S/{\sim_{\mathrm{row}}} S / ∼ row is bounded by n n n , since ≡ L \equiv_L ≡ L refines ∼ r o w \sim_{\mathrm{row}} ∼ row [24 Lem. 1] .
Dimension of orbits of S / ∼ r o w S/{\sim_{\mathrm{row}}} S / ∼ row is bounded by d d d , since supp ( [ u ] ∼ r o w ) ⊆ supp ( [ u ] ≡ L ) ⊆ supp ( u ) \operatorname{supp}([u]_{\sim_{\mathrm{row}}}) \subseteq\operatorname{supp}([u]_{\equiv_L}) \subseteq\operatorname{supp}(u) supp ([ u ] ∼ row ) ⊆ supp ([ u ] ≡ L ) ⊆ supp ( u ) [24 Lem. 2] .
Local symmetry of [ u ] ∼ r o w [u]_{\sim_{\mathrm{row}}} [ u ] ∼ row is a subgroup of S d S_d S d ; a strictly descending chain of such subgroups has length O ( d ) O(d) O ( d ) [2 ] , sharpening the log 2 d ! \log_2 d! log 2 d ! estimate used for this chain in [24 Lems. 5, 6] .
Each closedness step adds a row orbit, strictly increasing the first parameter; each consistency or counterexample step either increases the orbit count, increases a dimension, or strictly refines a local symmetry. Since all three parameters are bounded and advance monotonically, the loop terminates. The all-suffixes column extension of Algorithm 6 preserves this argument because, as noted above, handling a counterexample by columns still yields a strictly refined hypothesis, advancing one of the three parameters.
Equivalence queries. Each counterexample forces a strict refinement along one of the three axes, so the number of hypotheses, and hence of equivalence queries, is bounded by n + n ( d + O ( d ) ) = O ( n d ) n+n\left(d+O(d)\right)=O(nd) n + n ( d + O ( d ) ) = O ( n d ) (cf. [24 Lem. 5] ).
Membership queries. Since counterexamples extend only E E E , the set S S S grows solely by closedness promotions. Each promotion adds a row orbit lying in a fresh ∼ r o w \sim_{\mathrm{row}} ∼ row -class, and ∼ r o w \sim_{\mathrm{row}} ∼ row only refines as E E E grows, so N ( S / ∼ r o w ) N(S/\sim_{\mathrm{row}}) N ( S / ∼ row ) increases monotonically; as N ( S / ∼ r o w ) ≤ n N(S/\sim_{\mathrm{row}})\le n N ( S / ∼ row ) ≤ n by [24 Lem. 1] , there are at most n − 1 n-1 n − 1 promotions. Hence N ( S ) ≤ n N(S)\le n N ( S ) ≤ n , with representatives of length at most n − 1 n-1 n − 1 , so the words of S ∪ S ⋅ Σ S\cup S\cdot\Sigma S ∪ S ⋅ Σ have dimension at most e n en e n . Columns arise from two sources: a consistency defect adds one column and strictly refines the three termination parameters, so there are at most n ( d + O ( d ) + 1 ) = O ( n d ) n(d+O(d)+1)=O(nd) n ( d + O ( d ) + 1 ) = O ( n d ) such additions (cf. [24 Lem. 6] ); and each of the O ( n d ) O(nd) O ( n d ) counterexamples contributes at most m m m suffix orbits. Hence
N ( E ) = O ( ( m + 1 ) n d ) . N(E)=O\left((m+1)nd\right). N ( E ) = O ( ( m + 1 ) n d ) .
and every column has length at most m + O ( n d ) m+O(nd) m + O ( n d ) , since a column is either a suffix of a counterexample (of length at most m m m ) or extends an existing column by one letter through a consistency step; hence ℓ = m + O ( n d ) \ell=m+O(nd) ℓ = m + O ( n d ) , as claimed in Theorem 5.4, and every column has dimension at most e ℓ e\ell e ℓ . By [24 Lem. 7] , each orbit of S S S paired with each orbit of Σ \Sigma Σ splits into at most β ( e n , e ) \beta(en,e) β ( e n , e ) orbits of S ⋅ Σ S\cdot\Sigma S ⋅ Σ , so N ( S ⋅ Σ ) ≤ n N ( Σ ) β ( e n , e ) N(S\cdot\Sigma)\le nN(\Sigma)\beta(en,e) N ( S ⋅ Σ ) ≤ n N ( Σ ) β ( e n , e ) , and the table has
C = O ( n N ( Σ ) β ( e n , e ) ⋅ ( m + 1 ) n d ) C=O\left(nN(\Sigma)\beta(en,e)\cdot(m+1)nd\right) C = O ( n N ( Σ ) β ( e n , e ) ⋅ ( m + 1 ) n d )
(symbolic) cells. Filling one cell (the product of a row orbit of dimension at most e n en e n and a column orbit of dimension at most e ℓ e\ell e ℓ ) takes one membership query per coincidence pattern, i.e., at most β ( e n , e ℓ ) \beta(en,e\ell) β ( e n , e ℓ ) queries; this mirrors [24 Cor. 1] , whose second argument is likewise the column dimension. Multiplying the cell count C C C by the per-cell factor bounds the total by
O ( n 2 d ⋅ ( m + 1 ) ⋅ N ( Σ ) ⋅ β ( e n , e ) ⋅ β ( e n , e ℓ ) ) . O\left(n^{2}d\cdot(m+1)\cdot N(\Sigma)\cdot\beta(en,e)\cdot\beta(en,e\ell)\right). O ( n 2 d ⋅ ( m + 1 ) ⋅ N ( Σ ) ⋅ β ( e n , e ) ⋅ β ( e n , e ℓ ) ) .
the membership-query bound of Theorem 5.4. Note that only the cell count C C C is polynomial for a fixed alphabet dimension e e e (mirroring the corresponding remark in [24 ] ); the per-cell splitting factor β ( e n , e ℓ ) \beta(en,e\ell) β ( e n , e ℓ ) is factorial in the smaller of the observation dimensions e n en e n and e ℓ e\ell e ℓ .
Per-hypothesis runtime. Algorithm 5 issues one call to Quotient on S ∪ S ⋅ Σ S\cup S\cdot\Sigma S ∪ S ⋅ Σ . As established above, these words have length at most n n n , so their dimension is bounded by e n en e n . A row-equivalence test compares rows over E E E (whose columns have dimension at most e ℓ e\ell e ℓ ); each of the N ( E ) N(E) N ( E ) cells is a product orbit costing at most β ( e n , e ℓ ) \beta(en,e\ell) β ( e n , e ℓ ) coincidence-pattern inspections, according to Proposition 3.5 , so the test is an oracle of cost C ∼ r o w = O ( N ( E ) β ( e n , e ℓ ) ) C_{\sim_{\mathrm{row}}}=O(N(E)\,\beta(en,e\ell)) C ∼ row = O ( N ( E ) β ( e n , e ℓ )) . By Lemma 5.2, constructing the hypothesis therefore takes
O ( N ( S ∪ S ⋅ Σ ) 2 β ( e n , e n ) ( μ ( e n ) + C ∼ r o w ) ) . O\left(N(S\cup S\cdot\Sigma)^2\beta(en,en)\left(\mu(en)+C_{\sim_{\mathrm{row}}}\right)\right). O ( N ( S ∪ S ⋅ Σ ) 2 β ( e n , e n ) ( μ ( e n ) + C ∼ row ) ) .
which, since N ( S ∪ S ⋅ Σ ) = O ( n N ( Σ ) β ( e n , e ) ) N(S\cup S\cdot\Sigma)=O(nN(\Sigma)\beta(en,e)) N ( S ∪ S ⋅ Σ ) = O ( n N ( Σ ) β ( e n , e )) , is polynomial in N ( Σ ) N(\Sigma) N ( Σ ) and m m m but factorial in the observation dimensions e n en e n and e ℓ e\ell e ℓ , as stated. Outside the constant-time orbit-primitive model, constructing the orbit of a length-ℓ \ell ℓ word itself carries an additional Ω ( ℓ ) \Omega(\ell) Ω ( ℓ ) factor, as discussed in Appendix § 14 . Combining the query bounds with this per-hypothesis runtime yields the complexity stated in Theorem 5.4.
Our bounds are the strong-alphabet counterparts of the query-complexity analysis of [24 Sec. 4.3] , whose parameters n n n , k k k , p p p , l l l , and f A f_A f A correspond to our n n n , d d d , e e e , N ( Σ ) N(\Sigma) N ( Σ ) , and β \beta β . Two changes shift the bounds. First, Babai’s theorem [2 ] replaces the k log k k \log k k log k estimate for subgroup chains in [24 Lems. 5, 6] , sharpening the equivalence-query bound E n , k = O ( n k log k ) E_{n,k} = O(nk \log k) E n , k = O ( nk log k ) to O ( n d ) O(nd) O ( n d ) and the column count accordingly. Second, the counterexample handling is rebalanced: they extend the rows by all prefixes of a counterexample, so their rows number n + m E n , k n + mE_{n,k} n + m E n , k and reach dimension p ( n + m ) p(n + m) p ( n + m ) while their columns stay at length O ( n k log k ) O(nk \log k) O ( nk log k ) [24 Lem. 6] , whereas our all-suffix variant keeps O ( n ) O(n) O ( n ) rows of length at most n n n (dimension at most e n en e n ) and moves the counterexample length into the columns, of length at most ℓ = m + O ( n d ) \ell= m + O(nd) ℓ = m + O ( n d ) . In both cases, the membership-query bound is a cell count, polynomial in every parameter except the alphabet dimension ([24 Cor. 1] ; Theorem 5.4), times a per-cell factor factorial in the observation dimensions, which are p ( n + m ) p(n + m) p ( n + m ) and p n ( k + k log k + 1 ) pn(k + k \log k + 1) p n ( k + k log k + 1 ) for them and e n en e n and e ℓ e\ell e ℓ for us. Finally, the learned automaton differs: their ν L ∗ \nu L^* ν L ∗ returns the minimal nominal automaton itself, whereas our instantiation returns a strong lift of Corollary 4.5.
Full Experimental Data
This appendix collects the full numerical results underlying § 6 . All tables are machine-generated from the benchmark logs by our scripts.
Tools and Reproducibility
All experiments were conducted on the hardware and runtime versions reported in § 6 (Apple M1 Pro, macOS 26.5; Java SE 25.0.3, Scala 3.8.4, GHC 9.4.8, Apple clang 21.0.0, Z3 4.16.0). Each comparison tool was built from its public repository at the commit listed in Table 5 . The other tools (DEQ, Nλ, Lois, Ons, Ons-hs) were compiled as native ARM64 binaries; no memory limit was imposed on any non-JVM tool.
Table 5. Comparison tools and the exact versions used. Repositories are on GitHub unless noted.
The minimization and learning harnesses for Ons and Lois are taken from the ONS_Minimise4 repository (commit 11b8fe3), and the Ord learning baseline Ons additionally uses nominal-learning-ons5 (commit faffe8a). Under Ord, we report Ons-hs [40 ] as the primary baseline: it is the actively maintained Haskell successor to the C++ Ons library, selected for its active maintenance rather than any performance advantage. Both Ons and Ons-hs appear in the full tables in Table 9 and Table 10 . Since Namae supports both symmetries, the full results in Table 9 and Table 10 also include Namae under Ord, enabling a same-implementation comparison between Eq and Ord. The two symmetries share the runtime, the array representation, and the ν L ∗ \nu L^{*} ν L ∗ loop, but dispatch to symmetry-specific traits and implementations: under Ord, where local symmetries are trivial, language equivalence runs the orbit-wise breadth-first search with a visited set in place of a generating system, minimization follows the class-refinement algorithm of Ons-hs [40 ] , and quotients are computed by the support-intersection variant of Appendix H.1.
Table 9. Full minimization results across all benchmark languages (ww, Res, ResFIFO, MRes) and tools, under both the equality symmetry Eq (Namae, Nλ) and the total-order symmetry Ord (Namae, Ons, Ons-hs, Nλ, Lois); median of 3 runs. Nin/Nmin are the state orbit counts before/after minimization, dim the state dimension, and Δmin the size of the minimized transition function; times are in seconds, entries marked > 10 min hit the timeout, ‘—’ denotes values not measured or unavailable, and bold marks the fastest tool overall. Table 2 excerpts representative rows.
Table 10. Full ν L ∗ \nu L^* ν L ∗ learning results across all benchmark languages (ww, Res, ResFIFO) and tools, under both the equality symmetry Eq (Namae, N λ N_\lambda N λ ) and the total-order symmetry Ord (Namae, Ons, Ons-hs, N λ N_\lambda N λ ); median of 3 runs. N N N is the state orbit count of the target language, dim the state dimension, MQs the number of membership queries, and Δ \Delta Δ the size of the learned transition function; times are in seconds, entries marked > 10 min hit the timeout, ‘—’ denotes values not measured or unavailable, and bold marks the fastest tool overall. Table 3 excerpts representative rows.
Benchmark Languages
For the equivalence benchmarks, we follow [29 ] and use the following register automata:
stacks : A register automaton over the alphabet Σ = { Push ( a ) ∣ a ∈ N } ∪ { Pop ( a ) ∣ a ∈ N } \Sigma= \{\operatorname{Push}(a) \mid a \in\mathbb{N}\} \cup\{\operatorname{Pop}(a) \mid a \in\mathbb{N}\} Σ = { Push ( a ) ∣ a ∈ N } ∪ { Pop ( a ) ∣ a ∈ N } that recognizes valid sequences of stack operations, where n n n denotes the maximum capacity of the stack.
CPT : A register automaton over the alphabet Σ = { populate ( a ) ∣ a ∈ N } ∪ ⋃ 1 ≤ i ≤ n { t i ( a ) ∣ a ∈ N } \Sigma= \{\operatorname{populate}(a) \mid a \in\mathbb{N}\} \cup\bigcup_{1 \le i \le n} \{t_i(a) \mid a \in\mathbb{N}\} Σ = { populate ( a ) ∣ a ∈ N } ∪ ⋃ 1 ≤ i ≤ n { t i ( a ) ∣ a ∈ N } . This benchmark is designed to generate an exceptionally large number of partial permutations during bisimulation, thereby effectively demonstrating the power of the generating system.
Each instance compares two language-equivalent encodings, the worst case for a bisimulation-based check. We omit the suite’s third family, glolo , which relies on global freshness and thus has no orbit-finite nominal counterpart, as noted in § 5.1 .
For the minimization and learning benchmarks, besides Res ( n ) \operatorname{Res}(n) Res ( n ) and ResFIFO ( n ) \operatorname{ResFIFO}(n) ResFIFO ( n ) from § 6.3 , the full tables also include the double-word language w w ( n ) ww(n) w w ( n ) , and, for minimization only, MRes ( m ) \operatorname{MRes}(m) MRes ( m ) , whose multi-dimensional alphabet would otherwise require adapting every tool’s black-box learning harness. Specifically, these languages are defined as follows:
Res ( n ) \operatorname{Res}(n) Res ( n ) : A language over the alphabet Σ = { Open ( a ) ∣ a ∈ N } ∪ { Close ( a ) ∣ a ∈ N } \Sigma= \{\operatorname{Open}(a) \mid a \in\mathbb{N}\} \cup\{\operatorname{Close}(a) \mid a \in\mathbb{N}\} Σ = { Open ( a ) ∣ a ∈ N } ∪ { Close ( a ) ∣ a ∈ N } that models resource management. It accepts a trace if all opened resources are eventually closed. A trace is rejected if any of the following occur:
if a Close ( a ) \operatorname{Close}(a) Close ( a ) occurs for a resource a a a that is not currently open,
if an Open ( a ) \operatorname{Open}(a) Open ( a ) occurs for a resource a a a that is already open, or
if the number of concurrently open resources exceeds the capacity n n n .
ResFIFO ( n ) \operatorname{ResFIFO}(n) ResFIFO ( n ) : An order-sensitive FIFO variant of Res ( n ) \operatorname{Res}(n) Res ( n ) . It is similar to Res ( n ) \operatorname{Res}(n) Res ( n ) but additionally requires that resources are closed in the exact order they were opened.
MultiRes ( m , n ) \operatorname{MultiRes}(m,n) MultiRes ( m , n ) : A language that runs m m m independent copies of Res ( n ) \operatorname{Res}(n) Res ( n ) in parallel. Its alphabet consists of Open ( a ) \operatorname{Open}(a) Open ( a ) and Close ( a ) \operatorname{Close}(a) Close ( a ) where a ∈ ( N ⊔ { ⊥ } ) m a \in(\mathbb{N} \sqcup\{\bot\})^{m} a ∈ ( N ⊔ { ⊥ } ) m is a tuple with at least one non-⊥ \bot ⊥ component; for each component a i ≠ ⊥ a_i \ne\bot a i = ⊥ , the corresponding Open/Close operation is applied to the i i i -th copy of Res ( n ) \operatorname{Res}(n) Res ( n ) . The non-⊥ \bot ⊥ components need not be distinct: for example, Open ⟨ a , a ⟩ \operatorname{Open}\langle a,a\rangle Open ⟨ a , a ⟩ opens a a a in two copies at once. Since a a a carries up to m m m distinct atoms, its alphabet has dimension m m m . We write MRes ( m ) = MultiRes ( m , 1 ) \operatorname{MRes}(m) = \operatorname{MultiRes}(m,1) MRes ( m ) = MultiRes ( m , 1 ) for the single-capacity case used in the tables, whose input alphabet has dimension m m m ; larger capacities are supported by our harness but raise the state dimension to m n mn mn , which made benchmarking impractical within the timeout.
w w ( n ) ww(n) w w ( n ) : The double-word language { w w ∣ w ∈ N n } \{ww \mid w \in\mathbb{N}^{n}\} { w w ∣ w ∈ N n } of length 2 n 2n 2 n over the alphabet Σ = N \Sigma= \mathbb{N} Σ = N .
Regarding local symmetry, some states of the minimal automaton accepting Res ( n ) \operatorname{Res}(n) Res ( n ) carry the full symmetric group S n S_n S n as their local symmetry. In contrast, for the order-sensitive languages ResFIFO ( n ) \operatorname{ResFIFO}(n) ResFIFO ( n ) and w w ( n ) ww(n) w w ( n ) , the local symmetries of all states in their minimal automata are trivial. Consequently, the minimal automaton of ResFIFO ( n ) \operatorname{ResFIFO}(n) ResFIFO ( n ) is already strong, while a strong lift of Res ( n ) \operatorname{Res}(n) Res ( n ) ’s replaces each set of open resources by an ordered tuple, so the two strong lifts have isomorphic state spaces over Eq: tuples of at most n n n pairwise distinct open resources plus a rejecting sink. Since both transition functions are total and equivariant over the same state space and alphabet, their orbit counts coincide as well, so the two ν L ∗ \nu L^* ν L ∗ runs under Eq maintain observation tables of the same shape and are expected to issue the same number of membership queries, exactly as the identical MQ and Δ \Delta Δ columns of Table 3 and Table 10 show.
Running the Benchmarks
We report the median wall-clock time of three runs subject to a 10-minute timeout as detailed in § 6 . We use wall-clock time rather than the CPU-time convention of [40 ] , since for Namae JVM-internal CPU accounting cannot be cleanly separated from JIT and garbage-collection overhead, making wall-clock the fairer common measure across the JVM, Haskell, and C++ implementations compared here. The measurement boundary differs by task and is stated in each paragraph below. Wherever Namae is timed in-process (equivalence and minimization), JIT warm-up is excluded from the measurement. The warm-up exercises fixed small instances distinct from the measured one (a small stack pair for equivalence and w w ( 1 ) ww(1) w w ( 1 ) for minimization) within the same JVM as the subsequent measurement; the three measured runs use separate JVM invocations and share no JIT state. Excluding warm-up prevents JVM start-up and JIT compilation overhead from dominating the small-n n n measurements, which would otherwise exaggerate the gap to the natively compiled comparison tools; for large n n n this overhead is negligible and does not affect our conclusions. For each tool and benchmark family, we increase n n n until the first timeout, at which point neither the remaining repetitions at that n n n nor any larger n n n are attempted; every > 10 min entry in Table 9 and Table 10 therefore reflects a single timed-out run rather than a median of three.
Language equivalence. Following [29 ] , DEQ and Namae read the two register automata to be compared from XML files and decide their equivalence, whereas N λ \mathrm{N}\lambda N λ and Lois programmatically construct the automata and perform the equivalence check internally, as in the original benchmarks. Each tool internally measures the execution time of the equivalence check, excluding input parsing.
Minimization. Following [40 ] , each tool reads a serialized nominal automaton from a file, minimizes it, and serializes the result. We designed a custom serialization format for the Eq symmetry and patched N λ \mathrm{N}\lambda N λ to read it. The inputs are generated by Namae with a total transition function; for Ord, we take the Eq-generated input and split each orbit of dimension d d d in its states and the transition function’s domain into up to d ! d! d ! orbits, realizing the orbit-splitting of Remark 2.2. The output formats vary across tools: ONS-HS and N λ \mathrm{N}\lambda N λ emit their internal representations, ONS emits only the number of states, and Lois minimizes the state space only, without constructing the transition function; accordingly, the reported transition size Δ min \Delta_{\min} Δ m i n is the number of symbolic entries for N λ \mathrm{N}\lambda N λ , unavailable for Lois, and the number of orbits in the domain of the transition function for the others (Namae and ONS-HS). We check the correctness of each tool’s output by confirming that its reported minimized state count matches the expected N min N_{\min} N m i n . We measure each external tool’s process time; Namae’s in-process measurement still includes input parsing and output serialization. For reference, with JVM start-up and warm-up included, Namae takes 0.44 s instead of 0.06 s when minimizing Res(3), but 11.6 s instead of 11.13 s on Res(7); this in-process/external-process asymmetry favors Namae, though the baselines’ process start-up remains small against the multi-second runtimes at the scales where we draw our conclusions.
Learning. Following [40 ] , the teacher and the learner run as separate processes that communicate over standard input/output, ensuring a genuinely black-box learning setup; we reuse their communication protocol. Our teacher is implemented in Scala on top of Namae’s automaton representation; the stdin/stdout round-trip latency between teacher and learner is negligible against the measured runtimes. We measure the wall-clock time of the learner process uniformly for every learner, including Namae, unlike the in-process exception used for equivalence and minimization. The equivalence query returns a pre-computed counterexample, again as in [40 ] . As in minimization, the transition size Δ \Delta Δ is the number of symbolic entries for N λ N\lambda N λ and the number of orbits in the domain of the transition function for the others.
Full Results
For language equivalence, Figure 5 shows all four-tool comparisons on stacks and CPT, and Table 6 –Table 8 report the corresponding raw runtimes. For minimization and learning, Table 9 and Table 10 give the full results across all benchmark languages and tools: runtimes, orbit counts, and transition sizes (with membership-query counts for learning). On the shared Ord inputs, the differences between Namae and Ons-hs are implementation-level constants, in both directions: Ons-hs minimizes Res ( 4 ) \operatorname{Res}(4) Res ( 4 ) and Res ( 5 ) \operatorname{Res}(5) Res ( 5 ) about 6 × 6\times 6 × faster, whereas Namae learns Res ( 3 ) \operatorname{Res}(3) Res ( 3 ) about 10 × 10\times 10 × faster and completes ResFIFO ( 3 ) \operatorname{ResFIFO}(3) ResFIFO ( 3 ) learning where Ons-hs times out. Both swings are dwarfed by the symmetry effect visible within the same tables: on Res ( 5 ) \operatorname{Res}(5) Res ( 5 ) minimization, the same Namae code takes 0.26 0.26 0.26 s under Eq and 141.49 141.49 141.49 s under Ord.
Figure 5. Language equivalence runtimes on stacks n = 1 … 15 n = 1\ldots15 n = 1 … 15 , all four tools (seconds, log-log). (a) Namae vs. Nλ. (b) Namae vs. Lois. (c) Namae vs. DEQ on stacks n = 10 , … , 500 n = 10,\ldots,500 n = 10 , … , 500 . (d) Namae vs. DEQ on CPT n = 10 , … , 100 n = 10,\ldots,100 n = 10 , … , 100 .
Table 6 Language-equivalence runtimes on the stacks benchmark for n = 1 , … , 15 n = 1,\ldots,15 n = 1 , … , 15 , comparing Namae with DEQ, N Λ N_\Lambda N Λ , and Lois (median of 3 runs, seconds; entries marked > 10 > 10 > 10 min hit the timeout, ‘—’ denotes an instance not attempted after a smaller instance timed out, and 0.000 denotes a time below the 1 ms measurement resolution). These data underlie Figure 4 (a) and Figure 5 .
Table 6.
Figure 4. Language equivalence runtimes (log-log). (a) Namae vs. N λ N\lambda N λ on stacks n = 1 , … , 15 n=1,\ldots,15 n = 1 , … , 15 . (b) Namae vs. DEQ on stacks n = 10 , … , 500 n=10,\ldots,500 n = 10 , … , 500 . (c) Namae vs. DEQ on CPT n = 10 , … , 100 n=10,\ldots,100 n = 10 , … , 100 .
Table 8 Language-equivalence runtimes on the stacks benchmark for n = 1 , … , 15 n = 1,\ldots,15 n = 1 , … , 15 and n = 20 , 30 , … , 500 n = 20,30,\ldots,500 n = 20 , 30 , … , 500 , comparing Namae with DEQ (median of 3 runs, seconds). These data underlie Figure 4 (b).
Table 8.
Table 7 Language-equivalence runtimes on the CPT benchmark for n = 10 , 20 , … , 100 n = 10,20,\ldots,100 n = 10 , 20 , … , 100 , comparing Namae with DEQ (median of 3 runs, seconds). These data underlie Figure 4 (c).
Table 7.