# Algorithms for Inferring Register Automata - A Comparison of Existing Approaches

@inproceedings{Aarts2014AlgorithmsFI, title={Algorithms for Inferring Register Automata - A Comparison of Existing Approaches}, author={Fides Aarts and Falk Howar and Harco Kuppens and Frits W. Vaandrager}, booktitle={ISoLA}, year={2014} }

In recent years, two different approaches for learning register automata have been developed: as part of the LearnLib tool algorithms have been implemented that are based on the Nerode congruence for register automata, whereas the Tomte tool implements algorithms that use counterexample-guided abstraction refinement to automatically construct appropriate mappers. In this paper, we compare the LearnLib and Tomte approaches on a newly defined set of benchmarks and highlight their differences and… Expand

#### Figures, Tables, and Topics from this paper

#### 17 Citations

Benchmarks for Automata Learning and Conformance Testing

- Computer Science
- Models, Mindsets, Meta
- 2018

A large collection of benchmarks, publicly available through the wiki automata.cs.ru.nl, of different types of state machine models: DFAs, Moore machines, Mealy machines, interface automata and register automata will allow researchers to evaluate the performance of new algorithms and tools for active automata learning and conformance testing. Expand

Learning Register Automata with Fresh Value Generation

- Computer Science
- ICTAC
- 2015

We present a new algorithm for active learning of register automata. Our algorithm uses counterexample-guided abstraction refinement to automatically construct a component which maps in a history… Expand

Learning Nondeterministic Register Automata Using Mappers ⋆

- 2015

We present a new algorithm for active learning of register automata. Our algorithm uses counterexample-guided abstraction refinement to automatically construct a component which maps (in a history… Expand

Correctness and termination of Tomte components for active register automata learning

- 2015

In this thesis, we will analyze some of the components of the learning environment of the learning tool Tomte. This tool adds components to the learning environment, which enables it to learn a large… Expand

Foundations of active automata learning: an algorithmic perspective

- Computer Science, Mathematics
- 2015

One of the stated goals of this thesis is to change this situation, by giving a rigorously formal description of an approach to active automata learning that is independent of specific data structures or algorithmic realizations. Expand

Active Automata Learning in Practice - An Annotated Bibliography of the Years 2011 to 2016

- Computer Science
- Machine Learning for Dynamic Software Analysis
- 2018

The progress that has been made over the past five years is reviewed, the status of active automata learning techniques with respect to applications in the field of software engineering is assessed, and an updated agenda for future research is presented. Expand

RALib : A LearnLib extension for inferring EFSMs

- Mathematics
- 2015

Formal models are often used to describe the behavior of a computer program or component. Behavioral models have many different usages, e.g., in model-based techniques for software development and… Expand

Active Learning for Extended Finite State Machines 12

- 2015

We present a black-box active learning algorithm for inferring extended finite state machines (EFSM)s by dynamic black-box analysis. EFSMs can be used to model both data flow and control behavior of… Expand

Active learning for extended finite state machines

- Computer Science
- Formal Aspects of Computing
- 2016

A black-box active learning algorithm for inferring extended finite state machines (EFSM) by dynamic black- box analysis based on a novel learning model based on so-called tree queries that induces a generalization of the classical Nerode equivalence and canonical automata construction to the symbolic setting. Expand

Combining Black-Box and White-Box Techniques for Learning Register Automata

- Computer Science
- Computing and Software Science
- 2019

Some directions for future research on how black-box model learning can be enhanced using white-box information extraction methods are explored, with the aim to maintain the benefits of dynamic black- box methods while making effective use of information that can be obtained through white- box techniques. Expand

#### References

SHOWING 1-10 OF 47 REFERENCES

Inferring Canonical Register Automata

- Computer Science
- VMCAI
- 2012

This paper presents an extension of active automata learning to register automata, an automaton model which is capable of expressing the influence of data on control flow and drastically outperforms the classic L * algorithm, even when exploiting optimal data abstraction and symmetry reduction. Expand

Learning register automata: from languages to program structures

- Computer Science
- Machine Learning
- 2013

This paper reviews the development of Register Automaton learning, an enhancement of active automata learning to deal with infinite-state systems and focuses on a key problem to achieve practicality in this field: the adequate treatment of data values ranging over infinite domains. Expand

Automata Learning through Counterexample Guided Abstraction Refinement

- Computer Science
- FM
- 2012

This article shows how such abstractions can be constructed fully automatically for a restricted class of extended finite state machines in which one can test for equality of data parameters, but no operations on data are allowed. Expand

Inferring Semantic Interfaces of Data Structures

- Computer Science
- ISoLA
- 2012

This paper shows how to fully automatically infer semantic interfaces of data structures on the basis of systematic testing, and evaluates the algorithm on a complex data structure, a "stack of stacks", the largest of which it could learn in merely 20 seconds with less than 4000 membership queries. Expand

A succinct canonical register automaton model

- Computer Science
- J. Log. Algebraic Methods Program.
- 2015

A novel canonical automaton model, based on register automata, that can be used to specify protocol or program behavior, and can be exponentially more succinct than previous proposals, since it filters out ‘accidental’ relations between data values. Expand

Learning I/O Automata

- Computer Science
- CONCUR
- 2010

It is shown that, by exploiting links between three widely used modeling frameworks for reactive systems, any tool for active learning of Mealy machines can be used for learning I/O automata that are deterministic and output determined. Expand

Introduction to Active Automata Learning from a Practical Perspective

- Computer Science
- SFM
- 2011

In this chapter we give an introduction to active learning of Mealy machines, an automata model particularly suited for modeling the behavior of realistic reactive systems. Active learning is… Expand

Dynamic testing via automata learning

- Computer Science
- International Journal on Software Tools for Technology Transfer
- 2009

This paper presents dynamic testing, a method that exploits automata learning to systematically test (black box) systems almost without prerequisites. Based on interface descriptions and optional… Expand

Hybrid learning: interface generation through static, dynamic, and symbolic analysis

- Computer Science
- ISSTA
- 2013

The explosion of method sequences that learning generates to validate its computed interfaces is reduced through partial order reduction resulting from a static analysis of the component, and novel algorithms that are primarily based on dynamic, concrete component execution, while resorts to symbolic analysis on a limited, as needed, basis are proposed. Expand

Analysis of Recursive Game Graphs Using Data Flow Equations

- Computer Science
- VMCAI
- 2004

Given a finite-state abstraction of a sequential program with potentially recursive procedures and input from the environment, whether there are input sequences that can drive the system into “bad/good” executions is checked. Expand