Output-decomposed Learning of Mealy Machines

Rick Koenders; Joshua Moerman

doi:10.48550/arXiv.2405.08647

Output-decomposed Learning of Mealy Machines

Research output: Working paper / Preprint › Preprint › Academic

Abstract

We present an active automata learning algorithm which learns a decomposition of a finite state machine, based on projecting onto individual outputs. This is dual to a recent compositional learning algorithm by Labbaf et al. (2023). When projecting the outputs to a smaller set, the model itself is reduced in size. By having several such projections, we do not lose any information and the full system can be reconstructed. Depending on the structure of the system this reduces the number of queries drastically, as shown by a preliminary evaluation of the algorithm.

Original language	English
Publisher	Cornell University - arXiv
Number of pages	11
DOIs	https://doi.org/10.48550/arXiv.2405.08647
Publication status	Submitted - 14 May 2024

Keywords

Active Automata Learning
Model Learning
Compositionality
Finite State Machines

Access to Document

10.48550/arXiv.2405.08647

Cite this

@techreport{b19a7fa086744bd884a35eee1e83ccdb,

title = "Output-decomposed Learning of Mealy Machines",

abstract = "We present an active automata learning algorithm which learns a decomposition of a finite state machine, based on projecting onto individual outputs. This is dual to a recent compositional learning algorithm by Labbaf et al. (2023). When projecting the outputs to a smaller set, the model itself is reduced in size. By having several such projections, we do not lose any information and the full system can be reconstructed. Depending on the structure of the system this reduces the number of queries drastically, as shown by a preliminary evaluation of the algorithm.",

keywords = "Active Automata Learning, Model Learning, Compositionality, Finite State Machines",

author = "Rick Koenders and Joshua Moerman",

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 = "2024",

month = may,

day = "14",

doi = "10.48550/arXiv.2405.08647",

language = "English",

publisher = "Cornell University - arXiv",

address = "United States",

type = "WorkingPaper",

institution = "Cornell University - arXiv",

}

TY - UNPB

T1 - Output-decomposed Learning of Mealy Machines

AU - Koenders, Rick

AU - Moerman, Joshua

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 - 2024/5/14

Y1 - 2024/5/14

N2 - We present an active automata learning algorithm which learns a decomposition of a finite state machine, based on projecting onto individual outputs. This is dual to a recent compositional learning algorithm by Labbaf et al. (2023). When projecting the outputs to a smaller set, the model itself is reduced in size. By having several such projections, we do not lose any information and the full system can be reconstructed. Depending on the structure of the system this reduces the number of queries drastically, as shown by a preliminary evaluation of the algorithm.

AB - We present an active automata learning algorithm which learns a decomposition of a finite state machine, based on projecting onto individual outputs. This is dual to a recent compositional learning algorithm by Labbaf et al. (2023). When projecting the outputs to a smaller set, the model itself is reduced in size. By having several such projections, we do not lose any information and the full system can be reconstructed. Depending on the structure of the system this reduces the number of queries drastically, as shown by a preliminary evaluation of the algorithm.

KW - Active Automata Learning

KW - Model Learning

KW - Compositionality

KW - Finite State Machines

U2 - 10.48550/arXiv.2405.08647

DO - 10.48550/arXiv.2405.08647

M3 - Preprint

BT - Output-decomposed Learning of Mealy Machines

PB - Cornell University - arXiv

ER -

Output-decomposed Learning of Mealy Machines

Abstract

Keywords

Access to Document

Fingerprint

Cite this