Stefan Zetzsche ; Alexandra Silva ; Matteo Sammartino - Guarded Kleene Algebra with Tests: Automata Learning

entics:10505 - Electronic Notes in Theoretical Informatics and Computer Science, February 28, 2023, Volume 1 - Proceedings of MFPS XXXVIII - https://doi.org/10.46298/entics.10505
Guarded Kleene Algebra with Tests: Automata LearningArticle

Authors: Stefan Zetzsche ; Alexandra Silva ; Matteo Sammartino

    Guarded Kleene Algebra with Tests (GKAT) is the fragment of Kleene Algebra with Tests (KAT) that arises by replacing the union and iteration operations of KAT with predicate-guarded variants. GKAT is more efficiently decidable than KAT and expressive enough to model simple imperative programs, making it attractive for applications to e.g. network verification. In this paper, we further explore GKAT's automata theory, and present GL*, an algorithm for learning the GKAT automaton representation of a black-box, by observing its behaviour. A complexity analysis shows that it is more efficient to learn a representation of a GKAT program with GL* than with Angluin's existing L* algorithm. We implement GL* and L* in OCaml and compare their performances on example programs.


    Volume: Volume 1 - Proceedings of MFPS XXXVIII
    Published on: February 28, 2023
    Accepted on: December 20, 2022
    Submitted on: December 19, 2022
    Keywords: Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Automated Probabilistic Black-Box Verification; Funder: European Commission; Code: 101002697

    Consultation statistics

    This page has been seen 171 times.
    This article's PDF has been downloaded 99 times.