A Fresh Approach to Learning Register Automata

Benedikt Bollig, Peter Habermehl, Martin Leucker, Benjamin Monmege


This paper provides an Angluin-style learning algorithm for a class of register automata supporting the notion of fresh data values. More specifically, we introduce session automata which are well suited for modeling protocols in which sessions using fresh values are of major interest, like in security protocols or ad-hoc networks. We show that session automata (i)have an expressiveness partly extending, partly reducing that of register automata, (ii) admit a symbolic regular representation, and (iii) have a decidable equivalence and model-checking problem (unlike register automata).Using these results, we establish a learning algorithm to infer session automata through membership and equivalence queries. Finally, we strengthen the robustness of our automaton by its characterization in monadic second-order logic.

Original languageEnglish
Title of host publicationDevelopments in Language Theory
Number of pages13
VolumeLNCS 7907
Place of PublicationBerlin
PublisherSpringer Verlag
Publication date19.09.2013
ISBN (Print)978-3-642-38770-8
ISBN (Electronic)978-3-642-38771-5
Publication statusPublished - 19.09.2013
Event17th International Conference on Developments in Language Theory
- Marne-la-Vallee, France
Duration: 18.06.201321.06.2013
Conference number: 99421


Dive into the research topics of 'A Fresh Approach to Learning Register Automata'. Together they form a unique fingerprint.

Cite this