C. Ferretti, G. Mauri
Identifying unrecognizable regular languages by queries.
Abstract
We describe a new technique useful in identifying
a subclass of regular trace languages (defined on a free
partially commutative monoid). We extend
an algorithm defined by Dana Angluin in 1987 for DFA's
and using equivalence and membership queries.
In trace languages the words are
equivalence classes of strings, and we show how to extract, from a
given class, a string that can drive the original learning algorithm.
In this way we can identify a class of
regular trace languages which includes languages
which are not recognizable by any automaton.