Compositional learning of mutually recursive procedural systems

Simple item page
dc.contributor.authorFrohme, Markus
dc.contributor.authorSteffen, Bernhard
dc.date.accessioned2022-04-26T13:39:09Z
dc.date.available2022-04-26T13:39:09Z
dc.date.issued2021-10-05
dc.description.abstractThis paper presents a compositional approach to active automata learning of Systems of Procedural Automata (SPAs), an extension of Deterministic Finite Automata (DFAs) to systems of DFAs that can mutually call each other. SPAs are of high practical relevance, as they allow one to efficiently learn intuitive recursive models of recursive programs after an easy instrumentation that makes calls and returns observable. Key to our approach is the simultaneous inference of individual DFAs for each of the involved procedures via expansion and projection: membership queries for the individual DFAs are expanded to membership queries of the entire SPA, and global counterexample traces are transformed into counterexamples for the DFAs of concerned procedures. This reduces the inference of SPAs to a simultaneous inference of the DFAs for the involved procedures for which we can utilize various existing regular learning algorithms. The inferred models are easy to understand and allow for an intuitive display of the procedural system under learning that reveals its recursive structure. We implemented the algorithm within the LearnLib framework in order to provide a ready-to-use tool for practical application which is publicly available on GitHub for experimentation.en
dc.identifier.urihttp://hdl.handle.net/2003/40881
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-22738
dc.language.isoende
dc.relation.ispartofseriesInternational journal on software tools for technology transfer;Vol. 23. 2021, issue 4, pp 521-543
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.subjectActive automata learningen
dc.subjectProcedural systemsen
dc.subjectContext-free languagesen
dc.subjectVisibly pushdown languagesen
dc.subject.ddc004
dc.subject.rswkKontextfreie Sprachede
dc.subject.rswkDeterministischer endlicher Automatde
dc.titleCompositional learning of mutually recursive procedural systemsen
dc.typeTextde
dc.type.publicationtypearticlede
dcterms.accessRightsopen access
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primarycitationInternational journal on software tools for technology transfer. Vol. 23. 2021, issue 4, pp. 521-543en
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1007/s10009-021-00634-yde

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Frohme-Steffen2021_Article_CompositionalLearningOfMutuall.pdf
Size:
765.35 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

LS 05 Programmiersysteme