Learning nominal automata

Joshua Moerman; Matteo Sammartino; Alexandra Silva; Bartek Klin; Michal Szynwelski

doi:10.1145/3009837.3009879

Learning nominal automata

Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, Michal Szynwelski

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

Abstract

We present an Angluin-style algorithm to learn nominal automata, which are acceptors of languages over infinite (structured) alphabets. The abstract approach we take allows us to seamlessly extend known variations of the algorithm to this new setting. In particular we can learn a subclass of nominal non-deterministic automata. An implementation using a recently developed Haskell library for nominal computation is provided for preliminary experiments.

Original language	English
Title of host publication	POPL 2017
Subtitle of host publication	Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages
Editors	Giuseppe Castagna, Andrew D. Gordon
Publisher	Association for Computing Machinery
Pages	613-625
Number of pages	13
ISBN (Print)	978-1-4503-4660-3
DOIs	https://doi.org/10.1145/3009837.3009879
Publication status	Published - 2017
Event	44th ACM SIGPLAN Symposium on Principles of Programming Languages - Paris, France Duration: 15 Jan 2017 → 21 Jan 2017 Conference number: 44 https://dl.acm.org/doi/proceedings/10.1145/3009837

Symposium

Symposium	44th ACM SIGPLAN Symposium on Principles of Programming Languages
Abbreviated title	POPL '17
Country/Territory	France
City	Paris
Period	15/01/17 → 21/01/17
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3009837

Access to Document

10.1145/3009837.3009879

Cite this

@inproceedings{a59159aba8bc4028940f241992e3a094,

title = "Learning nominal automata",

abstract = "We present an Angluin-style algorithm to learn nominal automata, which are acceptors of languages over infinite (structured) alphabets. The abstract approach we take allows us to seamlessly extend known variations of the algorithm to this new setting. In particular we can learn a subclass of nominal non-deterministic automata. An implementation using a recently developed Haskell library for nominal computation is provided for preliminary experiments.",

author = "Joshua Moerman and Matteo Sammartino and Alexandra Silva and Bartek Klin and Michal Szynwelski",

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.; 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL '17 ; Conference date: 15-01-2017 Through 21-01-2017",

year = "2017",

doi = "10.1145/3009837.3009879",

language = "English",

isbn = " 978-1-4503-4660-3",

pages = "613--625",

editor = "Giuseppe Castagna and Gordon, {Andrew D.}",

booktitle = "POPL 2017",

publisher = "Association for Computing Machinery",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/3009837",

}

Moerman, J, Sammartino, M, Silva, A, Klin, B & Szynwelski, M 2017, Learning nominal automata. in G Castagna & AD Gordon (eds), POPL 2017: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. Association for Computing Machinery, pp. 613-625, 44th ACM SIGPLAN Symposium on Principles of Programming Languages, Paris, France, 15/01/17. https://doi.org/10.1145/3009837.3009879

Learning nominal automata. / Moerman, Joshua; Sammartino, Matteo; Silva, Alexandra et al.
POPL 2017: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. ed. / Giuseppe Castagna; Andrew D. Gordon. Association for Computing Machinery, 2017. p. 613-625.

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

TY - GEN

T1 - Learning nominal automata

AU - Moerman, Joshua

AU - Sammartino, Matteo

AU - Silva, Alexandra

AU - Klin, Bartek

AU - Szynwelski, Michal

N1 - Conference code: 44

PY - 2017

Y1 - 2017

N2 - We present an Angluin-style algorithm to learn nominal automata, which are acceptors of languages over infinite (structured) alphabets. The abstract approach we take allows us to seamlessly extend known variations of the algorithm to this new setting. In particular we can learn a subclass of nominal non-deterministic automata. An implementation using a recently developed Haskell library for nominal computation is provided for preliminary experiments.

AB - We present an Angluin-style algorithm to learn nominal automata, which are acceptors of languages over infinite (structured) alphabets. The abstract approach we take allows us to seamlessly extend known variations of the algorithm to this new setting. In particular we can learn a subclass of nominal non-deterministic automata. An implementation using a recently developed Haskell library for nominal computation is provided for preliminary experiments.

U2 - 10.1145/3009837.3009879

DO - 10.1145/3009837.3009879

M3 - Conference Article in proceeding

SN - 978-1-4503-4660-3

SP - 613

EP - 625

BT - POPL 2017

A2 - Castagna, Giuseppe

A2 - Gordon, Andrew D.

PB - Association for Computing Machinery

T2 - 44th ACM SIGPLAN Symposium on Principles of Programming Languages

Y2 - 15 January 2017 through 21 January 2017

ER -

Learning nominal automata

Abstract

Symposium

Access to Document

Fingerprint

Cite this