betaFeedback

WorksComputer Science

Efficient Nominal Automata Computation with Strong Nominal Sets

Abstract

Nominal automata and register automata are expressively equivalent models of computation over infinite alphabets, yet an algorithmic gap separates them in practice: dedicated algorithms decide language equivalence of deterministic register automata in polynomial time by working orbit-wise, while general-purpose nominal-computation tools that rely on SMT solvers hide the orbit structure and degrade rapidly even on small instances. We trace this gap to non-trivial local symmetries in nominal sets and observe that the configuration spaces of register automata correspond to strong nominal sets, whose elements carry only trivial local symmetries. We characterize strong nominal sets categorically, consolidating known and new equivalences, and derive a constraint-free array representation of orbit-finite strong nominal sets and equivariant maps; we further prove the existence of projective covers, guaranteeing that every nominal set admits a strong approximation preserving both orbit count and dimensions, computable for quotients of strong nominal sets. Building on these results, we develop concrete algorithms for language equivalence, minimization, and active learning, bridging the algorithmic gap for equivalence (in polynomial time for a fixed alphabet dimension) and extending the orbit-wise approach to minimization and learning. Finally, our implementation Namae, based on the array representation, outperforms existing nominal-computation tools and, at scale, stays within a small constant factor of a dedicated register-automaton equivalence tool.

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 q0q_0, q1q_1, q2q_2 and two registers x1x_1, x2x_2. An Open(aa) transition stores a new resource name aa in a vacant register, while a Close(aa)

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, q2q_2 needs two Close transitions, one of which reassigns the registers (x1:=x2x_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 dd then splits into up to 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\}; each such element is fixed by the non-trivial swap (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 (x1:=x2x_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:

SNom≃Kl⁡(T)≃Fam⁡(Iop)≃Proj⁡([I,Set])≃NSetfn\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}}

where SNom\mathbf{SNom} denotes the category of strong nominal sets and equivariant maps, I\mathbb{I} is the category of finite subsets of N\mathbb{N} and injections, TT is the monad induced by the adjunction between the category Nom\mathbf{Nom} of nominal sets and the functor category [ ⁣[I],Set][\![\mathbb{I}], \mathbf{Set}] [20, 33], Fam⁡(Iop)\operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) is the free coproduct completion of Iop\mathbb{I}^{\mathrm{op}}, Proj⁡([I,Set])\operatorname{Proj}([\mathbb{I}, \mathbf{Set}]) is the category of projective objects of [I,Set][\mathbb{I}, \mathbf{Set}], and NSetfn\mathbf{NSet}_{\mathrm{fn}} is the category of finitely named sets [25].

Crucially, the equivalence SNom≃Fam⁡(Iop)\mathbf{SNom} \simeq\operatorname{Fam}(\mathbb{I}^{\mathrm{op}}) yields the concrete, constraint-free array representation developed in § 3.2. In this representation, each orbit is determined solely by its dimension dd, an element is a dd-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\} by (a,b)∼(b,a)(a,b)\sim(b,a) yields {{a,b}∣a≠b}\{\{a,b\}\mid a\ne b\}, thereby introducing local symmetries. Consequently, the state space of a minimal nominal automaton generally falls outside SNom\mathrm{SNom}.

Beyond the equivalence SNom≃Proj⁡([I,Set])\mathrm{SNom}\simeq\operatorname{Proj}([\mathbb{I},\mathbf{Set}]), we show in Theorem 4.2 that every nominal set XX admits a strong approximation X′X', obtained from a projective cover in [I,Set][\mathbb{I},\mathbf{Set}]: the induced equivariant surjection p:X′↠Xp:X'\twoheadrightarrow X strips away local symmetries yet, by Theorem 4.3, merges no orbits and inflates no dimensions. Since transitions lift along pp 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' 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^* [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 Namae\mathrm{Namae}, and evaluated it in § 6. We confirmed that Namae\mathrm{Namae} outperforms the SMT-based tool Nλ\mathrm{N}\lambda and remains within a small constant factor of the dedicated register-automaton tool DEQ\mathrm{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:

  1. A categorical characterization of strong nominal sets, consolidating known and new equivalences into a single theorem (§ 3.1).

  2. An array representation for orbit-finite strong nominal sets and equivariant maps between them, derived from the SNom≃Fam(Πop)\mathrm{SNom}\simeq\mathrm{Fam}(\Pi^{\mathrm{op}}) equivalence (§ 3.2).

  3. An existence theorem for projective covers, guaranteeing that every nominal set admits a strong approximation preserving its orbit count and dimensions (§ 4).

  4. Concrete algorithms for language equivalence, minimization, and active learning on strong nominal automata, implemented in our library Namae\mathrm{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 GG, we write g1g2g_1g_2 for the multiplication (applying g2g_2 first), id\mathrm{id} for the unit, and H≤GH\leq G for a subgroup HH. For a set XX, the symmetric group Sym⁡(X)\operatorname{Sym}(X) consists of all permutations (bijections) of XX. We write N\mathbb{N} for the naturals and [n]={1,…,n}[n] = \{1,\ldots,n\}, and abbreviate the symmetric group on [n][n] as Sn=Sym⁡([n])S_n = \operatorname{Sym}([n]).

G-sets. A GG-set XX carries a group action ⋅:G×X→X\cdot: G \times X \to X. A map f:X→Yf: X \to Y between GG-sets is equivariant if f(g⋅x)=g⋅f(x)f(g \cdot x) = g \cdot f(x), and a subset A⊆XA \subseteq X is equivariant if g⋅A=Ag \cdot A = A for all g∈Gg \in G. The orbit of x∈Xx \in X is G⋅x={g⋅x∣g∈G}G \cdot x = \{g \cdot x \mid g \in G\}. We write orb⁡(X)\operatorname{orb}(X) for the set of orbits, so X=⨆O∈orb⁡(X)OX = \bigsqcup_{O \in\operatorname{orb}(X)} O. A GG-set XX is transitive (or a single orbit) if orb⁡(X)\operatorname{orb}(X) is a singleton.

Data symmetries and nominal sets. A data symmetry [9] is a pair S=(A,G)\mathcal{S} = (A, G) of a countably infinite set AA of atoms and a subgroup G≤Sym⁡(A)G \leq\operatorname{Sym}(A). We focus on two symmetries: the equality symmetry Eq=(N,Sym⁡(N))\mathsf{Eq} = (\mathbb{N}, \operatorname{Sym}(\mathbb{N})) and the total-order symmetry Ord=(Q,Aut⁡(Q,<))\mathsf{Ord} = (\mathbb{Q}, \operatorname{Aut}(\mathbb{Q}, <)), where Aut⁡(Q,<)\operatorname{Aut}(\mathbb{Q}, <) comprises all order-preserving permutations.

For a finite set C⊆AC \subseteq 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\}. We say CC supports an element xx of a GG-set if Fix⁡G(C)⊆Stab⁡G(x)\operatorname{Fix}_{G}(C) \subseteq\operatorname{Stab}_{G}(x), where Stab⁡G(x)={g∈G∣g⋅x=x}\operatorname{Stab}_{G}(x) = \{g \in G \mid g \cdot x = x\} is the stabilizer of xx. A nominal set over S\mathcal{S} is a GG-set where every element has a finite support. We denote by NomS\mathbf{Nom}_{\mathcal{S}} the category of nominal sets and equivariant maps, and by NomS1\mathbf{Nom}_{\mathcal{S}}^{1} its full subcategory of single-orbit nominal sets. A nominal set XX is orbit-finite if orb⁡(X)\operatorname{orb}(X) is finite; we write N(X)=∣orb⁡(X)∣N(X) = |\operatorname{orb}(X)| for its number of orbits. Over Eq\mathsf{Eq} and Ord\mathsf{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 xx in any nominal set has a unique least support supp⁡(x)\operatorname{supp}(x). Both Eq\mathsf{Eq} and Ord\mathsf{Ord} have this property [9, 40]. The dimension of xx is dim⁡(x)=∣supp⁡(x)∣\dim(x) = |\operatorname{supp}(x)|. Since supp⁡(g⋅x)=g⋅supp⁡(x)\operatorname{supp}(g \cdot x) = g \cdot\operatorname{supp}(x), all elements of an orbit OO share the same dimension, written dim⁡(O)\dim(O); for an orbit-finite set XX we define dim⁡(X)=max⁡O∈orb⁡(X)dim⁡(O)\dim(X) = \max_{O \in\operatorname{orb}(X)} \dim(O). The local symmetry of xx is the restriction Stab⁡G(x)∣supp⁡(x)\operatorname{Stab}_{G}(x)|_{\operatorname{supp}(x)} of its stabilizer to its least support; it is a subgroup of Sym⁡(supp⁡(x))\operatorname{Sym}(\operatorname{supp}(x)), since every g∈Stab⁡G(x)g \in\operatorname{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). When least supports exist, every single-orbit nominal set is determined up to isomorphism by a support representation (C,S)(C, S) of a finite support C⊆AC \subseteq A and a local symmetry group S≤Sym⁡(C)S \leq\operatorname{Sym}(C) [9 Prop. 9.15].

Example 2.1. We illustrate these notions over Eq\mathsf{Eq}:

  • The set of atoms N\mathbb{N} with action g⋅a=g(a)g \cdot a = g(a) is a single orbit (i.e., N(N)=1N(\mathbb{N}) = 1). Since supp⁡(a)={a}\operatorname{supp}(a) = \{a\}, it has dimension 1 and trivial local symmetry.

  • A product X×YX \times 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). Thus N2\mathbb{N}^{2} splits into two orbits: the diagonal {(a,a)∣a∈N}\{(a,a) \mid a \in\mathbb{N}\} of dimension 1, and the off-diagonal {(a,b)∣a≠b}\{(a,b) \mid a \ne 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\}. The set of two-element subsets {{a,b}∣a≠b}\{\{a,b\} \mid a \ne b\} forms a single orbit of dimension 2, with local symmetry Sym⁡({a,b})≅S2\operatorname{Sym}(\{a,b\}) \cong S_{2} swapping the atoms.

  • Any set XX with trivial action g⋅x=xg \cdot x = x is a nominal set with dimension 0.

Remark 2.2 (Local symmetry over Eq\mathsf{Eq} and Ord\mathsf{Ord}). Under Eq\mathsf{Eq}, a dimension-dd element can carry any local symmetry S≤Sym⁡([d])S \leq\operatorname{Sym}([d]); under Ord\mathsf{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 dd-tuples of distinct atoms, a single Eq\mathsf{Eq}-orbit of dimension dd with trivial local symmetry, splits into d!d! Ord\mathsf{Ord}-orbits when taken over the atoms Q\mathbb{Q} of Ord\mathsf{Ord}. For example, the off-diagonal {(a,b)∣a≠b}\{(a,b) \mid a \ne b\}, a single Eq\mathsf{Eq}-orbit, splits into {(a,b)∣a<b}\{(a,b) \mid a < b\} and {(a,b)∣a>b}\{(a,b) \mid a > b\} over Ord\mathsf{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⋅(a1⋯an)=(g⋅a1)⋯(g⋅an)g \cdot(a_1 \cdots a_n) = (g \cdot a_1) \cdots(g \cdot a_n); an equivariant language is an equivariant subset L⊆Σ∗L \subseteq\Sigma^*.

References

  1. [1]1 Dana Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87–106, 1987. doi:10.1016/0890-5401(87)90052–6.
  2. [2]2 László Babai. On the length of subgroup chains in the symmetric group. Communications in Algebra, 14(9):1729–1736, 1986. doi:10.1080/00927878608823393.
  3. [3]3 Mrudula Balachander, Emmanuel Filiot, Raffaella Gentilini, and Nikos Tzevelekos. Register automata with permutations. In 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, Warsaw, Poland, August 25-29, 2025, volume 345 of LIPIcs, pages 14:1–14:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.MFCS.2025.14.
  4. [4]4 Michael Benedikt, Clemens Ley, and Gabriele Puppis. What you must remember when processing data words. In Proceedings of the 4th Alberto Mendelzon International Workshop on Foundations of Data Management, Buenos Aires, Argentina, May 17-20, 2010, volume 619 of CEUR Workshop Proceedings. CEUR-WS.org, 2010. URL: https://ceur-ws.org/Vol-619/paper11.pdf.
  5. [5]5 Mikołaj Bojańczyk. Orbit-finite sets and their algorithms (invited talk). In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, July 10-14, 2017, volume 80 of LIPIcs, pages 1:1–1:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.1.
  6. [6]6 Mikołaj Bojańczyk. Slightly infinite sets. Draft, version September 11, 2019. Available at https://www.mimuw.edu.pl/~bojan/paper/atom-book, 2019.
  7. [7]7 Mikołaj Bojańczyk. Slightly infinite sets. Draft, version July 3, 2025. Available at https://www.mimuw.edu.pl/~bojan/paper/atom-book, 2025.
  8. [8]8 Mikołaj Bojańczyk, Laurent Braud, Bartek Klin, and Sławomir Lasota. Towards nominal computation. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA, January 22-28, 2012, pages 401–412. ACM, 2012. doi:10.1145/2103656.2103704.
  9. [9]9 Mikołaj Bojańczyk, Bartek Klin, and Sławomir Lasota. Automata theory in nominal sets. Log. Methods Comput. Sci., 10(3), 2014. doi:10.2168/LMCS-10(3:4)2014.
  10. [10]10 Mikołaj Bojańczyk and Sławomir Lasota. A machine-independent characterization of timed languages. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, volume 7392 of Lecture Notes in Computer Science, pages 92–103. Springer, 2012. doi:10.1007/978-3-642-31585-5_12.
  11. [11]11 Sofia Cassel, Falk Howar, Bengt Jonsson, and Bernhard Steffen. Learning extended finite state machines. In Software Engineering and Formal Methods - 12th International Conference, SEFM 2014, Grenoble, France, September 1-5, 2014, Proceedings, volume 8702 of Lecture Notes in Computer Science, pages 250–264. Springer, 2014. doi:10.1007/978-3-319-10431-7_18.DOI
  12. [12]12 Vincenzo Ciancia, Alexander Kurz, and Ugo Montanari. Families of symmetries as efficient models of resource binding. In Proceedings of the Tenth Workshop on Coalgebraic Methods in Computer Science, CMCS@ETAPS 2010, Paphos, Cyprus, March 26-28, 2010, volume 264 of Electronic Notes in Theoretical Computer Science, pages 63–81. Elsevier, 2010. doi: 10.1016/J.ENTCS.2010.07.014.DOI
  13. [13]13 Simon Dierl, Paul Fiterau-Brostean, Falk Howar, Bengt Jonsson, Konstantinos Sagonas, and Fredrik Tåquist. Scalable tree-based register automata learning. In Tools and Algorithms for the Construction and Analysis of Systems - 30th International Conference, TACAS 2024, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2024, Luxembourg City, Luxembourg, April 6-11, 2024, Proceedings, Part II, volume 14571 of Lecture Notes in Computer Science, pages 87–108. Springer, 2024. doi:10.1007/978-3-031-57249-4_5.
  14. [14]Gian-Luigi Ferrari, Ugo Montanari, and Marco Pistore. Minimizing transition systems for name passing calculi: A co-algebraic formulation. In Foundations of Software Science and Computation Structures, 5th International Conference, FOSSACS 2002. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002 Grenoble, France, April 8-12, 2002, Proceedings, volume 2303 of Lecture Notes in Computer Science, pages 129–158. Springer, 2002. doi:10.1007/3-540-45931-6_10.DOI
  15. [15]Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 36–41. IEEE Computer Society, 1980. doi:10.1109/SFCS.1980.34.DOI
  16. [16]Fabio Gadducci, Marino Miculan, and Ugo Montanari. About permutation algebras, (pre)sheaves and named sets. High. Order Symb. Comput., 19(2-3):283–304, 2006. doi:10.1007/S10990-006-8749-3.DOI
  17. [17]Michael Kaminski and Nissim Francez. Finite-memory automata. Theor. Comput. Sci., 134(2):329–363, 1994. doi:10.1016/0304-3975(94)90242-9.DOI
  18. [18]Bartek Klin and Michał Szynwelski. SMT solving for functional programming over infinite structures. In Proceedings 6th Workshop on Mathematically Structured Functional Programming, MSFP@ETAPS 2016, Eindhoven, Netherlands, 8th April 2016, volume 207 of EPTCS, pages 57–75, 2016. doi:10.4204/EPTCS.207.3.DOI
  19. [19]Eryk Kopczyński and Szymon Toruńczyk. LOIS: syntax and semantics. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017, pages 586–598. ACM, 2017. doi:10.1145/3009837.3009876.DOI
  20. [20]Alexander Kurz, Daniela Petrisan, and Jiří Velebil. Algebraic theories over nominal sets. CoRR, abs/1006.3027, 2010. arXiv:1006.3027.arxiv.org/abs/1006.3027
  21. [21]Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer, 2nd edition, 1998. doi:10.1007/978-1-4757-4721-8.
  22. [22]Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. Inf. Comput., 118(2):316–326, 1995. doi:10.1006/inco.1995.1070.DOI
  23. [23]Joshua Moerman and Jurriaan Rot. Separation and renaming in nominal sets. In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, Barcelona, Spain, January 13-16, 2020, volume 152 of LIPIcs, pages 31:1–31:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CSL.2020.31.arxiv.org/abs/1906.00763
  24. [24]Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, and Michał Szynwelski. Learning nominal automata. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017, pages 613–625. ACM, 2017. doi:10.1145/3009837.3009879.DOI
  25. [25]Ugo Montanari and Marco Pistore. An introduction to history dependent automata. In Second Workshop on Higher-Order Operational Techniques in Semantics, HOOTS 1997, Stanford, CA, USA, December 8-12, 1997, volume 10 of Electronic Notes in Theoretical Computer Science, pages 170–188. Elsevier, 1997. doi:10.1016/S1571-0661(05)80696-6.DOI
  26. [26]Edward F. Moore. Gedanken-experiments on sequential machines. In Claude E. Shannon and John McCarthy, editors, Automata Studies, volume 34 of Annals of Mathematics Studies, pages 129–153. Princeton University Press, 1956. doi:10.1515/9781400882618-006.DOI
  27. [27]Andrzej S. Murawski, Steven J. Ramsay, and Nikos Tzevelekos. Bisimilarity in fresh-register automata. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 156–167. IEEE Computer Society, 2015. doi:10.1109/LICS.2015.24.DOI
  28. [28]Andrzej S. Murawski, Steven J. Ramsay, and Nikos Tzevelekos. Polynomial-time equivalence testing for deterministic fresh-register automata. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, August 27-31, 2018, volume 117 of LIPIcs, pages 72:1–72:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.MFCS.2018.72.DOI
  29. [29]Andrzej S. Murawski, Steven J. Ramsay, and Nikos Tzevelekos. DEQ: equivalence checker for deterministic register automata. In Automated Technology for Verification and Analysis - 17th International Symposium, ATVA 2019, Taipei, Taiwan, October 28-31, 2019, Proceedings, volume 11781 of Lecture Notes in Computer Science, pages 350–356. Springer, 2019. doi: 10.1007/978-3-030-31784-3_20.DOI
  30. [30]Andrzej S. Murawski, Steven J. Ramsay, and Nikos Tzevelekos. Bisimilarity in fresh-register automata. Log. Methods Comput. Sci., 21(1), 2025. doi:10.46298/LMCS-21(1:13)2025.DOI
  31. [31]Andrzej S. Murawski and Nikos Tzevelekos. Nominal game semantics. Found. Trends Program. Lang., 2(4):191–269, 2016. doi:10.1561/2500000017.DOI
  32. [32]Joanna Ochremiak. Nominal sets over algebraic atoms. In Relational and Algebraic Methods in Computer Science - 14th International Conference, RAMiCS 2014, Marienstatt, Germany, April 28-May 1, 2014. Proceedings, volume 8428 of Lecture Notes in Computer Science, pages 429–445. Springer, 2014. doi:10.1007/978-3-319-06251-8_26.DOI
  33. [33]Daniela Luana Petrişan. Investigations into Algebra and Topology over Nominal Sets. PhD thesis, University of Leicester, 2012. URL: https://hdl.handle.net/2381/10187.
  34. [34]Andrew M. Pitts. Nominal Sets: Names and Symmetry in Computer Science, volume 57 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2013. doi:10.1017/CBO9781139084673.DOI
  35. [35]Ronald L. Rivest and Robert E. Schapire. Inference of finite automata using homing sequences. Inf. Comput., 103(2):299–347, 1993. doi:10.1006/INCO.1993.1021.DOI
  36. [36]Samuel Staton. Name-passing process calculi: operational models and structural operational semantics. PhD thesis, University of Cambridge, 2007. doi:10.48456/tr-688.DOI
  37. [37]Nikos Tzevelekos. Full abstraction for nominal general references. In 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 10-12 July 2007, Wroclaw, Poland, Proceedings, pages 399–410. IEEE Computer Society, 2007. doi:10.1109/LICS.2007.21.DOI
  38. [38]Nikos Tzevelekos. Nominal Game Semantics. DPhil thesis, University of Oxford, 2008. URL: https://ora.ox.ac.uk/objects/uuid:c725f13-4523-4892-8ad1-8cff13637724.
  39. [39]Nikos Tzevelekos. Fresh-register automata. In Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 295–306. ACM, 2011. doi:10.1145/1926385.1926420.DOI
  40. [40]David Venhoek, Joshua Moerman, and Jurriaan Rot. Fast computations on ordered nominal sets. Theor. Comput. Sci., 935:82–104, 2022. doi:10.1016/J.TCS.2022.09.002.DOI
  41. [41]Thorsten Wißmann. Supported sets - A new foundation for nominal sets and automata. In 31st EACSL Annual Conference on Computer Science Logic, CSL 2023, Warsaw, Poland, February 13-16, 2023, volume 252 of LIPIcs, pages 38:1–38:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.CSL.2023.38.

Paper details

vlnc:W_pqdd6dfp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents