Fast Computations on Ordered Nominal Sets

David Venhoek, Joshua Moerman, Jurriaan Rot

Research output: Chapter in Book/Report/Conference proceedingConference Article in proceedingAcademicpeer-review


We show how to compute efficiently with nominal sets over the total order symmetry, by developing a direct representation of such nominal sets and basic constructions thereon. In contrast to previous approaches, we work directly at the level of orbits, which allows for an accurate complexity analysis. The approach is implemented as the library Ons (Ordered Nominal Sets).

Our main motivation is nominal automata, which are models for recognising languages over infinite alphabets. We evaluate Ons in two applications: minimisation of automata and active automata learning. In both cases, Ons is competitive compared to existing implementations and outperforms them for certain classes of inputs.
Original languageEnglish
Title of host publicationTheoretical Aspects of Computing- ICTAC 2018
Subtitle of host publication15th International Colloquium
EditorsBernd Fischer, Tarmo Uustalu
Number of pages20
ISBN (Electronic)978-3-030-02508-3
ISBN (Print)978-3-030-02507-6
Publication statusPublished - 2018
Externally publishedYes
Event15th International Colloquium on Theoretical Aspects of Computing - Stellenbosch, South Africa
Duration: 16 Oct 201819 Oct 2018
Conference number: 15

Publication series

SeriesLecture Notes in Computer Science
SeriesTheoretical Computer Science and General Issues (LNCS subseries)


Conference15th International Colloquium on Theoretical Aspects of Computing
Abbreviated titleICTAC 2018
Country/TerritorySouth Africa
Internet address


Dive into the research topics of 'Fast Computations on Ordered Nominal Sets'. Together they form a unique fingerprint.

Cite this