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

Ferretti, C., Mauri, G. (1994). Identifying unrecognizable regular languages by queries. In Proceedings of European Conference on Machine Learning, ECML-94, Catania, Italy, April 6–8, 1994 (pp.355-358). Berlin : Springer [10.1007/3-540-57868-4_72].

Identifying unrecognizable regular languages by queries

FERRETTI, CLAUDIO;MAURI, GIANCARLO
1994

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
slide + paper
trace languages; computational learning
English
ECML – European Conference on Machine Learning
1994
Proceedings of European Conference on Machine Learning, ECML-94, Catania, Italy, April 6–8, 1994
978-3-540-57868-0
1994
784
355
358
none
Ferretti, C., Mauri, G. (1994). Identifying unrecognizable regular languages by queries. In Proceedings of European Conference on Machine Learning, ECML-94, Catania, Italy, April 6–8, 1994 (pp.355-358). Berlin : Springer [10.1007/3-540-57868-4_72].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/17486
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
Social impact