Document Open Access Logo

CALF: Categorical Automata Learning Framework

Authors Gerco van Heerdt, Matteo Sammartino, Alexandra Silva

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.29.pdf
  • Filesize: 0.65 MB
  • 24 pages

Document Identifiers

Author Details

Gerco van Heerdt
Matteo Sammartino
Alexandra Silva

Cite As Get BibTex

Gerco van Heerdt, Matteo Sammartino, and Alexandra Silva. CALF: Categorical Automata Learning Framework. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 29:1-29:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CSL.2017.29

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.

Subject Classification

Keywords
  • automata learning
  • category theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dana Angluin. A note on the number of queries needed to identify regular languages. Inform. Control, 51:76-87, 1981. URL: http://dx.doi.org/10.1016/S0019-9958(81)90090-5.
  2. Dana Angluin. Learning regular sets from queries and counterexamples. Inform. Comput., 75:87-106, 1987. URL: http://dx.doi.org/10.1016/0890-5401(87)90052-6.
  3. Dana Angluin, Sarah Eisenstat, and Dana Fisman. Learning regular languages via alternating automata. In IJCAI, pages 3308-3314, 2015. Google Scholar
  4. Dana Angluin and Dana Fisman. Learning regular omega languages. In ALT, volume 8776, pages 125-139, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11662-4_10.
  5. Michael A. Arbib and H. Paul Zeiger. On the relevance of abstract algebra to control theory. Automatica, 5:589-606, 1969. URL: http://dx.doi.org/10.1016/0005-1098(69)90026-0.
  6. José L. Balcázar, Josep Díaz, Ricard Gavaldà, and Osamu Watanabe. Algorithms for learning finite automata from queries: A unified view. In Advances in Algorithms, Languages, and Complexity, pages 53-72. Springer, 1997. Google Scholar
  7. Therese Berg, Olga Grinchtein, Bengt Jonsson, Martin Leucker, Harald Raffelt, and Bernhard Steffen. On the correspondence between conformance testing and regular inference. In FASE, volume 3442, pages 175-189, 2005. URL: http://dx.doi.org/10.1007/978-3-540-31984-9_14.
  8. Francesco Bergadano and Stefano Varricchio. Learning behaviors of automata from multiplicity and equivalence queries. SIAM Journal on Computing, 25(6):1268-1280, 1996. URL: http://dx.doi.org/10.1137/S009753979326091X.
  9. Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of NFA. In IJCAI, volume 9, pages 1004-1009, 2009. Google Scholar
  10. Benedikt Bollig, Peter Habermehl, Martin Leucker, and Benjamin Monmege. A fresh approach to learning register automata. In DLT, volume 7907, pages 118-130, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38771-5_12.
  11. Sofia Cassel, Falk Howar, Bengt Jonsson, and Bernhard Steffen. Active learning for extended finite state machines. FAC, 28(2):233-263, 2016. URL: http://dx.doi.org/10.1007/s00165-016-0355-5.
  12. Martin Chapman, Hana Chockler, Pascal Kesseli, Daniel Kroening, Ofer Strichman, and Michael Tautschnig. Learning the language of error. In ATVA, volume 9364, pages 114-130. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-24953-7_9.
  13. Chia Yuan Cho, Domagoj Babić, Eui Chul Richard Shin, and Dawn Song. Inference and analysis of formal models of botnet command and control protocols. In CCS, pages 426-439. ACM, 2010. URL: http://dx.doi.org/10.1145/1866307.1866355.
  14. Tsun S. Chow. Testing software design modeled by finite-state machines. IEEE Trans. Software Eng., 4:178-187, 1978. URL: http://dx.doi.org/10.1109/TSE.1978.231496.
  15. Joeri de Ruiter and Erik Poll. Protocol state fuzzing of TLS implementations. In USENIX Security, pages 193-206, 2015. Google Scholar
  16. E. Mark Gold. System identification via state characterization. Automatica, 8:621-636, 1972. Google Scholar
  17. Bin-Lun Ho. On effective construction of realizations from input-output descriptions. PhD thesis, Stanford University, 1966. Google Scholar
  18. Malte Isberner. Foundations of active automata learning: an algorithmic perspective. PhD thesis, Technical University of Dortmund, 2015. Google Scholar
  19. Bart Jacobs and Alexandra Silva. Automata learning: A categorical perspective. In Horizons of the Mind, volume 8464, pages 384-406, 2014. URL: http://dx.doi.org/10.1007/978-3-319-06880-0_20.
  20. Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT press, 1994. Google Scholar
  21. David Lee and Mihalis Yannakakis. Testing finite-state machines: State identification and verification. IEEE T. Comput., 43:306-320, 1994. URL: http://dx.doi.org/10.1109/12.272431.
  22. Gang Luo, Alexandre Petrenko, and Gregor v. Bochmann. Selecting test sequences for partially-specified nondeterministic finite state machines. In Protocol Test Systems, pages 95-110. Springer, 1995. Google Scholar
  23. Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. Inform. and Comput., 118:316-326, 1995. URL: http://dx.doi.org/10.1006/inco.1995.1070.
  24. Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, and Michał Szynwelski. Learning nominal automata. In POPL, pages 613-625, 2017. Google Scholar
  25. Edward F. Moore. Gedanken-experiments on sequential machines. Automata studies, 34:129-153, 1956. Google Scholar
  26. Anil Nerode. Linear automaton transformations. Proceedings of the AMS, 9:541-544, 1958. Google Scholar
  27. Mathijs Schuts, Jozef Hooman, and Frits Vaandrager. Refactoring of legacy software using model learning and equivalence checking: an industrial experience report. In IFM, volume 9681, pages 311-325, 2016. URL: http://dx.doi.org/10.1007/978-3-319-33693-0_20.
  28. Rick Smetsers, Joshua Moerman, and David N. Jansen. Minimal separating sequences for all pairs of states. In LATA, pages 181-193, 2016. URL: http://dx.doi.org/10.1007/978-3-319-30000-9_14.
  29. Gerco van Heerdt. An abstract automata learning framework. Master’s thesis, Radboud University Nijmegen, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact