A robust class of data languages and an application to learning

DOI10.2168/LMCS-10(4:19)2014MaRDI QIDQ2938772zbMATH OpenOpenAlexFDO

Authors Benedikt Bollig, Peter Habermehl, Martin Leucker, Benjamin Monmege

Publication date 15 January 2015

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.6646

zbMATH Keywords

Angluin-style learningdata wordsfreshnessregister automata

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45)

Abstract: We introduce session automata, an automata model to process data words, i.e., words over an infinite alphabet. Session automata support the notion of fresh data values, 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. Session automata have an expressiveness partly extending, partly reducing that of classical register automata. We show that, unlike register automata and their various extensions, session automata are robust: They (i) are closed under intersection, union, and (resource-sensitive) complementation, (ii) admit a symbolic regular representation, (iii) have a decidable inclusion problem (unlike register automata), and (iv) enjoy logical characterizations. Using these results, we establish a learning algorithm to infer session automata through membership and equivalence queries.

Recommendations

• A fresh approach to learning register automata
• Learning Transparent Data Automata
• Inferring canonical register automata
• A succinct canonical register automaton model
• A Succinct Canonical Register Automaton Model

Cited in

(12)

• Nominal automata with name binding
• Polynomial-time equivalence testing for deterministic fresh-register automata
• Residuality and learning for nondeterministic nominal automata
• scientific article; zbMATH DE number 7559500 (Why is no real title available?)
• A Kleene theorem for nominal automata
• A fresh approach to learning register automata
• A Note on C² Interpreted over Finite Data-Words
• On-the-fly bisimilarity checking for fresh-register automata
• Learning deterministic variable automata over infinite alphabets
• Nominal tree automata with name allocation
• Variable automata over infinite alphabets
• Quantified data automata for linear data structures: a register automaton model with applications to learning invariants of programs manipulating arrays and lists

Describes a project that uses

Uses Software

• libalf

This page was built for publication: A robust class of data languages and an application to learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938772)