nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Angluin Learning via Logic

verfasst von : Simone Barlocco, Clemens Kupke

Erschienen in: Logical Foundations of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we will provide a fresh take on Dana Angluin’s algorithm for learning using ideas from coalgebraic modal logic. Our work opens up possibilities for applications of tools & techniques from modal logic to automata learning and vice versa. As main technical result we obtain a generalisation of Angluin’s original algorithm from DFAs to coalgebras for an arbitrary finitary set functor T in the following sense: given a (possibly infinite) pointed T-coalgebra that we assume to be regular (i.e. having an equivalent finite representation) we can learn its finite representation by asking (i) “logical queries” (corresponding to membership queries) and (ii) making conjectures to which the teacher has to reply with a counterexample. This covers (a known variant) of the original L* algorithm and the learning of Mealy/Moore machines. Other examples are bisimulation quotients of (probabilistic) transition systems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Sequent-Calculus Based Formulation of the Extended First Epsilon Theorem

Nächstes Kapitel A Universal Algebra for the Variable-Free Fragment of

Readers should think of “behavioural equivalence” as a general notion of bisimilarity. In all concrete examples in this paper both notions of equivalence coincide.

Instead, we could use triples \((S,\varSigma ,\models _S)\) to be in line with [6] but we decided to leave the third “bookkeeping” component implicit.

Jacobs, B.: Introduction to Coalgebra: Towards Mathematics of States and Observation. Cambridge Tracts in TCS. Cambridge University Press, New York (2016)MATH

Jacobs, B., Silva, A.: Automata learning: a categorical perspective. In: van Breugel, F., Kashefi, E., Palamidessi, C., Rutten, J. (eds.) Horizons of the Mind. A Tribute to Prakash Panangaden. LNCS, vol. 8464, pp. 384–406. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06880-0_20 CrossRef

van Heerdt, G.: An abstract automata learning framework. Master’s thesis, Radboud Universiteit Nijmegen (2016)

Moerman, J., Sammartino, M., Silva, A., Klin, B., Szynwelski, M.: Learning nominal automata. In: POPL 2017 (2017)

van Heerdt, G., Sammartino, M., Silva, A.: Learning automata with side-effects. CoRR abs/1704.08055 (2017)

Angluin, D.: Learning regular sets from queries and counter examples. Inf. Comput. 75(2), 87–106 (1987)MathSciNetCrossRefMATH

Adámek, J., Milius, S., Moss, L.S., Sousa, L.: Well-pointed coalgebras. Logical Methods Comput. Sci. 9(3) (2013)

Grädel, E., Thomas, W., Wilke, T. (eds.): Automata Logics, and Infinite Games. LNCS, vol. 2500. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36387-4 MATH

Mac Lane, S.: Categories for the Working Mathematician. Graduate Texts in Mathematics, vol. 5. Springer, New York (1971). https://doi.org/10.1007/978-1-4757-4721-8 CrossRefMATH

10.

Jacobs, B., Rutten., J.: An introduction to (co)algebras and (co)induction. In: Advanced Topics in Bisimulation and Coinduction. Cambridge Tracts in Theoretical Computer Science, vol. 5, pp. 38–99. Cambridge University Press (2011)

11.

Adámek, J., Trnková, V.: Automata and Algebras in Categories. Kluwer Academic Publishers, Dordrecht (1990)MATH

12.

Cirstea, C., Kurz, A., Pattinson, D., Schröder, L., Venema, Y.: Modal logics are coalgebraic. Comput. J. 54(1), 31–41 (2009)CrossRef

13.

Kupke, C., Pattinson, D.: Coalgebraic semantics of modal logics: an overview. Theoret. Comput. Sci. 412(38), 5070–5094 (2011)MathSciNetCrossRefMATH

14.

Schröder, L.: Expressivity of coalgebraic modal logic: the limits and beyond. Theoret. Comput. Sci. 390(2), 230–247 (2008)MathSciNetCrossRefMATH

15.

Hansen, H.H., Rutten, J.J.M.M.: Symbolic synthesis of mealy machines from arithmetic bitstream functions. Sci. Ann. Comp. Sci. 20, 97–130 (2010)MathSciNet

16.

Desharnais, J., Edalat, A., Panangaden, P.: Bisimulation for labelled markov processes. Inf. Comput. 179(2), 163–193 (2002)MathSciNetCrossRefMATH

17.

Kupke, C., Leal, R.A.: Characterising behavioural equivalence: three sides of one coin. In: Kurz, A., Lenisa, M., Tarlecki, A. (eds.) CALCO 2009. LNCS, vol. 5728, pp. 97–112. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03741-2_8 CrossRef

18.

Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge Tracts in Theoretical Computer Science, vol. 53. Cambridge University Press, New York (2001)CrossRefMATH

19.

Maler, O., Pnueli, A.: On the learnability of infinitary regular sets. Inf. Comput. 118(2), 316–326 (1995)MathSciNetCrossRefMATH

20.

Balle, B., Castro, J., Gavald, R.: Learning probabilistic automata: a study in state distinguishability. TCS 473, 46–60 (2013)MathSciNetCrossRefMATH

21.

Mao, H., Chen, Y., Jaeger, M., Nielsen, T.D., Larsen, K.G., Nielsen, B.: Learning probabilistic automata for model checking. In: 2011 Eighth International Conference on Quantitative Evaluation of Systems, pp. 111–120 (2011)

22.

Tzeng, W.G.: Learning probabilistic automata and markov chains via queries. Mach. Learn. 8(2), 151–166 (1992)MATH

23.

Sokolova, A.: Probabilistic systems coalgebraically: a survey. TCS 412(38), 5095–5110 (2011)MathSciNetCrossRefMATH

24.

Glück, R., Möller, B., Sintzoff, M.: Model refinement using bisimulation quotients. In: Johnson, M., Pavlovic, D. (eds.) AMAST 2010. LNCS, vol. 6486, pp. 76–91. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-17796-5_5 CrossRef

25.

Ghilardi, S.: Continuity, freeness, and filtrations. J. Appl. Non Class. Logics 20(3), 193–217 (2010)MathSciNetCrossRefMATH

26.

Bezhanishvili, G., Bezhanishvili, N., Iemhoff, R.: Stable canonical rules. J. Symbol. Logic 81(1), 284–315 (2016)MathSciNetCrossRefMATH

Titel: Angluin Learning via Logic
verfasst von: Simone Barlocco
Clemens Kupke
Verlag: Springer International Publishing
Buch: Logical Foundations of Computer Science
Print ISBN: 978-3-319-72055-5

Electronic ISBN: 978-3-319-72056-2

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-72056-2_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"