Fast Computations on Ordered Nominal Sets

David Venhoek, Joshua Moerman, Jurriaan Rot

Research output: Working paper / PreprintPreprintAcademic


Nominal automata are models for recognising languages over infinite alphabets, based on the algebraic notion of nominal set. Motivated by their use in automata theory, we show how to compute efficiently with nominal sets over the so-called total order symmetry, a variant which allows to compare alphabet letters for equality as well as their respective order. We develop an explicit finite representation of such nominal sets and basic constructions thereon. The approach is implemented as the library Ons (Ordered Nominal Sets), enabling programming with infinite sets. Returning to our motivation of nominal automata, 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
PublisherCornell University - arXiv
Number of pages38
Publication statusPublished - 16 Aug 2022

Publication series

SeriesComputing Research Repository


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

    Venhoek, D., Moerman, J. & Rot, J., 31 Oct 2022, In: Theor. Comput. Sci.. 935, p. 82-104 23 p.

    Research output: Contribution to journalArticleAcademicpeer-review

    Open Access
  • Fast Computations on Ordered Nominal Sets

    Venhoek, D., Moerman, J. & Rot, J., 2018, Theoretical Aspects of Computing- ICTAC 2018: 15th International Colloquium. Fischer, B. & Uustalu, T. (eds.). Springer, p. 493-512 20 p. (Lecture Notes in Computer Science, Vol. 11187). (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 11187).

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

Cite this