|
NeuroCOLT
Technical Report NC-TR-95-030
Identifying Regular
Languages over Partially-Commutative Monoids
Claudio
Ferretti and Giancarlo Mauri
Università di Milano
Italy
Abstract
We define a new technique useful in identifying a subclass of regular
languages defined on a free partially commutative monoid (regular
trace languages), using equivalence and membership queries. Our algorithm
extends an algorithm defined by Dana Angluin in 1987 to learn DFA's.
The words of a trace language can be seen as equivalence classes of
strings. We show how to extract, from a given equivalence class, a
string of an unknown underlying regular langu age. These strings can
drive the original learning algorithm which identify a regular string
language that defines also the target trace language. In this way
the algorithm applies also to classes of unrecognizable regular trace
languages and, as a corollary, to a class of unrecognizable string
languages. We also discuss bounds on the number of examples needed
to identify the target language and on the time required to process
them.
Download Compressed
Postscript
|