Research Results

The researchers Pierre Ganty, Elena Gutiérrez and Pedro Valero have recently published “A Quasiorder-based Perspective in Residual Automata” presented at MFCS 2020 (Mathematical Foundations of Computer Science) that took place from the 24th-28th of August. The three researchers of the IMDEA Software Institute propose a different view on a class of finite-state machines of great relevance in practice, the so-called “Residual Automata”.

To give a little bit of context, residual automata are classical finite-state automata (FSAs for short), i.e., transition systems with a finite number of states that are used to represent the so-called regular languages, one of the most studied objects in formal language theory.

Actually, finite-state automata are finite representations of regular languages, and this might not be illuminating but it is rather helpful when the languages they represent are infinite!

Going back to our objects, residual automata, among the general FSAs, enjoy interesting properties that make them useful in applications such as grammar inference.

The main goal of grammar inference is to find a target language using a finite set of examples of words in the language. In other words, grammar inference is a machine learning technique by means of which we learn a (possibly infinite) language of words given only a finite number of them.

In this context, residual automata are useful tools as it has been proven that they can represent very concisely (and finitely, since they are FSAs) the target language.

In this paper, they study the properties of residual automata from a theoretical point of view.

Namely, we use quasiorders as a mathematical tool to give a new perspective on the construction of residual automata. Quasiorders are relations between the elements of a set satisfying some properties. For instance, given the set of all natural numbers N, the relation ≤, which relates two elements x and y if x ≤ y, is a quasiorder on N.

In this work, they define quasiorders on words and use them to construct residual automata. By using different quasiorders we construct different residual automata, including the minimal one for some given language.

Concretely, we present a new residualization operation and a generalized Brzozowski’s method for building the minimal residual automaton for a given language. We also leverage this technique to offer a new perspective on NL*, an online learning algorithm for residual automata.