Fast Computations on Ordered Nominal Sets

David Venhoek; Joshua Moerman; Jurriaan Rot

doi:10.1007/978-3-030-02508-3_26

Fast Computations on Ordered Nominal Sets

David Venhoek
, Joshua Moerman
, Jurriaan Rot

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

Abstract

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 language	English
Title of host publication	Theoretical Aspects of Computing- ICTAC 2018
Subtitle of host publication	15th International Colloquium
Editors	Bernd Fischer, Tarmo Uustalu
Publisher	Springer
Pages	493-512
Number of pages	20
ISBN (Electronic)	978-3-030-02508-3
ISBN (Print)	978-3-030-02507-6
DOIs	https://doi.org/10.1007/978-3-030-02508-3_26
Publication status	Published - 2018
Externally published	Yes
Event	15th International Colloquium on Theoretical Aspects of Computing - Stellenbosch, South Africa Duration: 16 Oct 2018 → 19 Oct 2018 Conference number: 15 https://www.ictac.org.za/ https://link.springer.com/book/10.1007/978-3-030-02508-3

Publication series

Series	Lecture Notes in Computer Science
Volume	11187
ISSN	0302-9743

Series	Theoretical Computer Science and General Issues (LNCS subseries)
Volume	11187

Conference

Conference	15th International Colloquium on Theoretical Aspects of Computing
Abbreviated title	ICTAC 2018
Country/Territory	South Africa
City	Stellenbosch
Period	16/10/18 → 19/10/18
Internet address	https://www.ictac.org.za/ https://link.springer.com/book/10.1007/978-3-030-02508-3

Access to Document

10.1007/978-3-030-02508-3_26

1 Article
1 Preprint

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 journal › Article › Academic › peer-review

Open Access
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

Cite this

Venhoek, David ; Moerman, Joshua ; Rot, Jurriaan. / Fast Computations on Ordered Nominal Sets. Theoretical Aspects of Computing- ICTAC 2018: 15th International Colloquium. editor / Bernd Fischer ; Tarmo Uustalu. Springer, 2018. pp. 493-512 (Lecture Notes in Computer Science, Vol. 11187). (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 11187).

@inproceedings{b78d30a8882840f3b1dc5172eb52d37a,

title = "Fast Computations on Ordered Nominal Sets",

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

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.; 15th International Colloquium on Theoretical Aspects of Computing, ICTAC 2018 ; Conference date: 16-10-2018 Through 19-10-2018",

year = "2018",

doi = "10.1007/978-3-030-02508-3\_26",

language = "English",

isbn = "978-3-030-02507-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "493--512",

editor = "Bernd Fischer and Tarmo Uustalu",

booktitle = "Theoretical Aspects of Computing- ICTAC 2018",

address = "United States",

url = "https://www.ictac.org.za/, https://link.springer.com/book/10.1007/978-3-030-02508-3",

}

Venhoek, D, Moerman, J & Rot, J 2018, Fast Computations on Ordered Nominal Sets. in B Fischer & T Uustalu (eds), Theoretical Aspects of Computing- ICTAC 2018: 15th International Colloquium. Springer, Lecture Notes in Computer Science, vol. 11187, Theoretical Computer Science and General Issues (LNCS subseries), vol. 11187, pp. 493-512, 15th International Colloquium on Theoretical Aspects of Computing, Stellenbosch, South Africa, 16/10/18. https://doi.org/10.1007/978-3-030-02508-3_26

Fast Computations on Ordered Nominal Sets. / Venhoek, David; Moerman, Joshua; Rot, Jurriaan.
Theoretical Aspects of Computing- ICTAC 2018: 15th International Colloquium. ed. / Bernd Fischer; Tarmo Uustalu. Springer, 2018. p. 493-512 (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

TY - GEN

T1 - Fast Computations on Ordered Nominal Sets

AU - Venhoek, David

AU - Moerman, Joshua

AU - Rot, Jurriaan

N1 - Conference code: 15

PY - 2018

Y1 - 2018

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

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

U2 - 10.1007/978-3-030-02508-3_26

DO - 10.1007/978-3-030-02508-3_26

M3 - Conference Article in proceeding

SN - 978-3-030-02507-6

T3 - Lecture Notes in Computer Science

SP - 493

EP - 512

BT - Theoretical Aspects of Computing- ICTAC 2018

A2 - Fischer, Bernd

A2 - Uustalu, Tarmo

PB - Springer

T2 - 15th International Colloquium on Theoretical Aspects of Computing

Y2 - 16 October 2018 through 19 October 2018

ER -

Venhoek D, Moerman J, Rot J. Fast Computations on Ordered Nominal Sets. In Fischer B, Uustalu T, editors, Theoretical Aspects of Computing- ICTAC 2018: 15th International Colloquium. Springer. 2018. p. 493-512. (Lecture Notes in Computer Science, Vol. 11187). (Theoretical Computer Science and General Issues (LNCS subseries), Vol. 11187). doi: 10.1007/978-3-030-02508-3_26

Fast Computations on Ordered Nominal Sets

Abstract

Publication series

Conference

Access to Document

Fingerprint

Research output

Fast computations on ordered nominal sets

Fast Computations on Ordered Nominal Sets

Cite this