License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.29
URN: urn:nbn:de:0030-drops-76950
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7695/
Go to the corresponding LIPIcs Volume Portal

van Heerdt, Gerco ; Sammartino, Matteo ; Silva, Alexandra

CALF: Categorical Automata Learning Framework

pdf-format:
LIPIcs-CSL-2017-29.pdf (0.7 MB)

Abstract

Automata learning is a technique that has successfully been applied in verification, with the automaton type varying depending on the application domain. Adaptations of automata learning algorithms for increasingly complex types of automata have to be developed from scratch because there was no abstract theory offering guidelines. This makes it hard to devise such algorithms, and it obscures their correctness proofs. We introduce a simple category-theoretic formalism that provides an appropriately abstract foundation for studying automata learning. Furthermore, our framework establishes formal relations between algorithms for learning, testing, and minimization. We illustrate its generality with two examples: deterministic and weighted automata.

BibTeX - Entry

@InProceedings{vanheerdt_et_al:LIPIcs:2017:7695,
  author =	{Gerco van Heerdt and Matteo Sammartino and Alexandra Silva},
  title =	{{CALF: Categorical Automata Learning Framework}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{29:1--29:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7695},
  URN =		{urn:nbn:de:0030-drops-76950},
  doi =		{10.4230/LIPIcs.CSL.2017.29},
  annote =	{Keywords: automata learning, category theory}
}

Keywords: automata learning, category theory
Collection: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 16.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI