Fast computations on ordered nominal sets

David Venhoek; Joshua Moerman; Jurriaan Rot

doi:10.1016/j.tcs.2022.09.002

Fast computations on ordered nominal sets

David Venhoek
, Joshua Moerman^*
, Jurriaan Rot

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

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 language	English
Pages (from-to)	82-104
Number of pages	23
Journal	Theor. Comput. Sci.
Volume	935
DOIs	https://doi.org/10.1016/j.tcs.2022.09.002
Publication status	Published - 31 Oct 2022

Keywords

Automata learning
Automata theory
Minimisation
Nominal sets

Access to Document

10.1016/j.tcs.2022.09.002Licence: Free by publisher

1 Conference Article in proceeding
1 Preprint

Fast Computations on Ordered Nominal Sets
Venhoek, D., Moerman, J. & Rot, J., 16 Aug 2022, Cornell University - arXiv, 38 p. (Computing Research Repository).
Research output: Working paper / Preprint › Preprint

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 proceeding › Conference Article in proceeding › Academic › peer-review

Cite this

@article{7083554b88e14065b5ad13f0bb45bac5,

title = "Fast computations on ordered nominal sets",

abstract = "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.",

keywords = "Automata learning, Automata theory, Minimisation, Nominal sets",

author = "David Venhoek and Joshua Moerman and Jurriaan Rot",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2022",

month = oct,

day = "31",

doi = "10.1016/j.tcs.2022.09.002",

language = "English",

volume = "935",

pages = "82--104",

journal = "Theor. Comput. Sci.",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Fast computations on ordered nominal sets

AU - Venhoek, David

AU - Moerman, Joshua

AU - Rot, Jurriaan

N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2022/10/31

Y1 - 2022/10/31

N2 - 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.

AB - 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.

KW - Automata learning

KW - Automata theory

KW - Minimisation

KW - Nominal sets

U2 - 10.1016/j.tcs.2022.09.002

DO - 10.1016/j.tcs.2022.09.002

M3 - Article

SN - 0304-3975

VL - 935

SP - 82

EP - 104

JO - Theor. Comput. Sci.

JF - Theor. Comput. Sci.

ER -

Fast computations on ordered nominal sets

Abstract

Keywords

Access to Document

Fingerprint

Research output

Fast Computations on Ordered Nominal Sets

Fast Computations on Ordered Nominal Sets

Cite this