Learning weighted automata over principal ideal domains

Gerco van Heerdt; Clemens Kupke; Jurriaan Rot; Alexandra Silva

doi:10.1007/978-3-030-45231-5_31

Learning weighted automata over principal ideal domains

Gerco van Heerdt, Clemens Kupke, Jurriaan Rot, Alexandra Silva

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

13 Citations (Scopus)

61 Downloads (Pure)

Abstract

In this paper, we study active learning algorithms for weighted automata over a semiring. We show that a variant of Angluin’s seminal L⋆ algorithm works when the semiring is a principal ideal domain, but not for general semirings such as the natural numbers.

Original language	English
Title of host publication	Foundations of Software Science and Computation Structures
Subtitle of host publication	23rd International Conference, FOSSACS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25–30, 2020, Proceedings
Editors	Jean Goubault-Larrecq, Barbara König
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	602-621
Number of pages	20
ISBN (Electronic)	978-3-030-45231-5
ISBN (Print)	978-3-030-45230-8
DOIs	https://doi.org/10.1007/978-3-030-45231-5_31
Publication status	Published - 17 Apr 2020
Event	23rd International Conference, Foundations of Software Science and Computation Structures 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020. - Dublin, Ireland Duration: 25 Apr 2020 → 30 Apr 2020 https://etaps.org/2020/fossacs

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12077

Conference

Conference	23rd International Conference, Foundations of Software Science and Computation Structures 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020.
Abbreviated title	FOSSACS
Country/Territory	Ireland
City	Dublin
Period	25/04/20 → 30/04/20
Internet address	https://etaps.org/2020/fossacs

Keywords

weighted automata
automata learning

Access to Document

10.1007/978-3-030-45231-5_31Licence: CC BY 4.0

van-Heerdt-etal-FOSSACS-2020-Learning-weighted-automata-over-principleFinal published version, 4.99 MBLicence: CC BY 4.0

Cite this

van Heerdt, G., Kupke, C., Rot, J., & Silva, A. (2020). Learning weighted automata over principal ideal domains. In J. Goubault-Larrecq, & B. König (Eds.), Foundations of Software Science and Computation Structures: 23rd International Conference, FOSSACS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25–30, 2020, Proceedings (pp. 602-621). (Lecture Notes in Computer Science; Vol. 12077). Springer. https://doi.org/10.1007/978-3-030-45231-5_31

van Heerdt, Gerco ; Kupke, Clemens ; Rot, Jurriaan et al. / Learning weighted automata over principal ideal domains. Foundations of Software Science and Computation Structures: 23rd International Conference, FOSSACS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25–30, 2020, Proceedings. editor / Jean Goubault-Larrecq ; Barbara König. Cham, Switzerland : Springer, 2020. pp. 602-621 (Lecture Notes in Computer Science).

@inproceedings{83912b1a25264903a3849718ed578f2d,

title = "Learning weighted automata over principal ideal domains",

abstract = "In this paper, we study active learning algorithms for weighted automata over a semiring. We show that a variant of Angluin{\textquoteright}s seminal L⋆ algorithm works when the semiring is a principal ideal domain, but not for general semirings such as the natural numbers.",

keywords = "weighted automata, automata learning",

author = "\{van Heerdt\}, Gerco and Clemens Kupke and Jurriaan Rot and Alexandra Silva",

year = "2020",

month = apr,

day = "17",

doi = "10.1007/978-3-030-45231-5\_31",

language = "English",

isbn = "978-3-030-45230-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "602--621",

editor = "Jean Goubault-Larrecq and Barbara K{\"o}nig",

booktitle = "Foundations of Software Science and Computation Structures",

address = "Switzerland",

note = "23rd International Conference, Foundations of Software Science and Computation Structures 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020., FOSSACS ; Conference date: 25-04-2020 Through 30-04-2020",

url = "https://etaps.org/2020/fossacs",

}

van Heerdt, G, Kupke, C, Rot, J & Silva, A 2020, Learning weighted automata over principal ideal domains. in J Goubault-Larrecq & B König (eds), Foundations of Software Science and Computation Structures: 23rd International Conference, FOSSACS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25–30, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12077, Springer, Cham, Switzerland, pp. 602-621, 23rd International Conference, Foundations of Software Science and Computation Structures 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020., Dublin, Ireland, 25/04/20. https://doi.org/10.1007/978-3-030-45231-5_31

Learning weighted automata over principal ideal domains. / van Heerdt, Gerco; Kupke, Clemens; Rot, Jurriaan et al.
Foundations of Software Science and Computation Structures: 23rd International Conference, FOSSACS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25–30, 2020, Proceedings. ed. / Jean Goubault-Larrecq; Barbara König. Cham, Switzerland: Springer, 2020. p. 602-621 (Lecture Notes in Computer Science; Vol. 12077).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - Learning weighted automata over principal ideal domains

AU - van Heerdt, Gerco

AU - Kupke, Clemens

AU - Rot, Jurriaan

AU - Silva, Alexandra

PY - 2020/4/17

Y1 - 2020/4/17

N2 - In this paper, we study active learning algorithms for weighted automata over a semiring. We show that a variant of Angluin’s seminal L⋆ algorithm works when the semiring is a principal ideal domain, but not for general semirings such as the natural numbers.

AB - In this paper, we study active learning algorithms for weighted automata over a semiring. We show that a variant of Angluin’s seminal L⋆ algorithm works when the semiring is a principal ideal domain, but not for general semirings such as the natural numbers.

KW - weighted automata

KW - automata learning

UR - https://arxiv.org/abs/1911.04404

U2 - 10.1007/978-3-030-45231-5_31

DO - 10.1007/978-3-030-45231-5_31

M3 - Conference contribution book

SN - 978-3-030-45230-8

T3 - Lecture Notes in Computer Science

SP - 602

EP - 621

BT - Foundations of Software Science and Computation Structures

A2 - Goubault-Larrecq, Jean

A2 - König, Barbara

PB - Springer

CY - Cham, Switzerland

T2 - 23rd International Conference, Foundations of Software Science and Computation Structures 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020.

Y2 - 25 April 2020 through 30 April 2020

ER -

van Heerdt G, Kupke C, Rot J, Silva A. Learning weighted automata over principal ideal domains. In Goubault-Larrecq J, König B, editors, Foundations of Software Science and Computation Structures: 23rd International Conference, FOSSACS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25–30, 2020, Proceedings. Cham, Switzerland: Springer. 2020. p. 602-621. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-45231-5_31

Learning weighted automata over principal ideal domains

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this