Compositional Automata Learning of Synchronous Systems

Thomas Neele; Matteo Sammartino

doi:10.1007/978-3-031-30826-0_3

Compositional Automata Learning of Synchronous Systems

Thomas Neele (Corresponding author), Matteo Sammartino

Formal System Analysis

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

6 Citations (Scopus)

1 Downloads (Pure)

Abstract

Automata learning is a technique to infer an automaton model of a black-box system via queries to the system. In recent years it has found widespread use both in industry and academia, as it enables formal verification when no model is available or it is too complex to create one manually. In this paper we consider the problem of learning the individual components of a black-box synchronous system, assuming we can only query the whole system. We introduce a compositional learning approach in which several learners cooperate, each aiming to learn one of the components. Our experiments show that, in many cases, our approach requires significantly fewer queries than a widely-used non-compositional algorithm such as L^∗.

Original language	English
Title of host publication	Fundamental Approaches to Software Engineering
Subtitle of host publication	26th International Conference, FASE 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings
Editors	Leen Lambers, Sebastián Uchitel
Place of Publication	Cham
Publisher	Springer
Pages	47-66
Number of pages	20
ISBN (Electronic)	978-3-031-30826-0
ISBN (Print)	978-3-031-30825-3
DOIs	https://doi.org/10.1007/978-3-031-30826-0_3
Publication status	Published - 20 Apr 2023
Event	26th International Conference on Fundamental Approaches to Software Engineering, FASE 2023, held as part of the 26th European Joint Conferences on Theory and Practice of Software, ETAPS 2023 - Paris, France Duration: 22 Apr 2023 → 27 Apr 2023

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	13991
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Conference on Fundamental Approaches to Software Engineering, FASE 2023, held as part of the 26th European Joint Conferences on Theory and Practice of Software, ETAPS 2023
Country/Territory	France
City	Paris
Period	22/04/23 → 27/04/23

Funding

Acknowledgements. We thank the anonymous reviewers for their useful comments, and Tobias Kappéfor suggesting several improvements. This research was partially supported by the EPSRC Standard Grant CLeVer (EP/S028641/1).

Funders	Funder number
Engineering and Physical Sciences Research Council	EP/S028641/1

Access to Document

10.1007/978-3-031-30826-0_3

pdfFinal published version, 610 KBLicence: CC BY

Cite this

Neele, T., & Sammartino, M. (2023). Compositional Automata Learning of Synchronous Systems. In L. Lambers, & S. Uchitel (Eds.), Fundamental Approaches to Software Engineering: 26th International Conference, FASE 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings (pp. 47-66). (Lecture Notes in Computer Science (LNCS); Vol. 13991). Springer. https://doi.org/10.1007/978-3-031-30826-0_3

Neele, Thomas ; Sammartino, Matteo. / Compositional Automata Learning of Synchronous Systems. Fundamental Approaches to Software Engineering: 26th International Conference, FASE 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings. editor / Leen Lambers ; Sebastián Uchitel. Cham : Springer, 2023. pp. 47-66 (Lecture Notes in Computer Science (LNCS)).

@inproceedings{f4a281ddb0454c6a8d1cc201dab19c31,

title = "Compositional Automata Learning of Synchronous Systems",

abstract = "Automata learning is a technique to infer an automaton model of a black-box system via queries to the system. In recent years it has found widespread use both in industry and academia, as it enables formal verification when no model is available or it is too complex to create one manually. In this paper we consider the problem of learning the individual components of a black-box synchronous system, assuming we can only query the whole system. We introduce a compositional learning approach in which several learners cooperate, each aiming to learn one of the components. Our experiments show that, in many cases, our approach requires significantly fewer queries than a widely-used non-compositional algorithm such as L∗.",

author = "Thomas Neele and Matteo Sammartino",

year = "2023",

month = apr,

day = "20",

doi = "10.1007/978-3-031-30826-0_3",

language = "English",

isbn = "978-3-031-30825-3",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "47--66",

editor = "Leen Lambers and Sebasti{\'a}n Uchitel",

booktitle = "Fundamental Approaches to Software Engineering",

address = "Germany",

note = "26th International Conference on Fundamental Approaches to Software Engineering, FASE 2023, held as part of the 26th European Joint Conferences on Theory and Practice of Software, ETAPS 2023 ; Conference date: 22-04-2023 Through 27-04-2023",

}

Neele, T & Sammartino, M 2023, Compositional Automata Learning of Synchronous Systems. in L Lambers & S Uchitel (eds), Fundamental Approaches to Software Engineering: 26th International Conference, FASE 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings. Lecture Notes in Computer Science (LNCS), vol. 13991, Springer, Cham, pp. 47-66, 26th International Conference on Fundamental Approaches to Software Engineering, FASE 2023, held as part of the 26th European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, 22/04/23. https://doi.org/10.1007/978-3-031-30826-0_3

Compositional Automata Learning of Synchronous Systems. / Neele, Thomas (Corresponding author); Sammartino, Matteo.
Fundamental Approaches to Software Engineering: 26th International Conference, FASE 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings. ed. / Leen Lambers; Sebastián Uchitel. Cham: Springer, 2023. p. 47-66 (Lecture Notes in Computer Science (LNCS); Vol. 13991).

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

TY - GEN

T1 - Compositional Automata Learning of Synchronous Systems

AU - Neele, Thomas

AU - Sammartino, Matteo

PY - 2023/4/20

Y1 - 2023/4/20

N2 - Automata learning is a technique to infer an automaton model of a black-box system via queries to the system. In recent years it has found widespread use both in industry and academia, as it enables formal verification when no model is available or it is too complex to create one manually. In this paper we consider the problem of learning the individual components of a black-box synchronous system, assuming we can only query the whole system. We introduce a compositional learning approach in which several learners cooperate, each aiming to learn one of the components. Our experiments show that, in many cases, our approach requires significantly fewer queries than a widely-used non-compositional algorithm such as L∗.

AB - Automata learning is a technique to infer an automaton model of a black-box system via queries to the system. In recent years it has found widespread use both in industry and academia, as it enables formal verification when no model is available or it is too complex to create one manually. In this paper we consider the problem of learning the individual components of a black-box synchronous system, assuming we can only query the whole system. We introduce a compositional learning approach in which several learners cooperate, each aiming to learn one of the components. Our experiments show that, in many cases, our approach requires significantly fewer queries than a widely-used non-compositional algorithm such as L∗.

UR - http://www.scopus.com/inward/record.url?scp=85161457667&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-30826-0_3

DO - 10.1007/978-3-031-30826-0_3

M3 - Conference contribution

AN - SCOPUS:85161457667

SN - 978-3-031-30825-3

T3 - Lecture Notes in Computer Science (LNCS)

SP - 47

EP - 66

BT - Fundamental Approaches to Software Engineering

A2 - Lambers, Leen

A2 - Uchitel, Sebastián

PB - Springer

CY - Cham

T2 - 26th International Conference on Fundamental Approaches to Software Engineering, FASE 2023, held as part of the 26th European Joint Conferences on Theory and Practice of Software, ETAPS 2023

Y2 - 22 April 2023 through 27 April 2023

ER -

Neele T, Sammartino M. Compositional Automata Learning of Synchronous Systems. In Lambers L, Uchitel S, editors, Fundamental Approaches to Software Engineering: 26th International Conference, FASE 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings. Cham: Springer. 2023. p. 47-66. (Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-3-031-30826-0_3

Compositional Automata Learning of Synchronous Systems

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this