Identification of biRFSA languages

Abstract : The task of identifying a language from a set of its words is not an easy one. For instance, it is not feasible to identify regular languages in the general case. Therefore, looking for subclasses of regular languages that can be identi?ed in this framework is an interesting problem. One of the most classical identi?able classes is the class of reversible languages, introduced by D. Angluin, also called bideterministic languages as they can be represented by deterministic automata (DFA) whose reverse is also deterministic. Residual Finite State Automata (RFSA) on the other hand is a class of non deterministic automata that shares some properties with DFA. In particular, DFA are RFSA and RFSA can be much smaller. We study here learnability of the class of languages that can be represented by biRFSA: RFSA whose reverse are RFSA. We prove that this class is not identi?able in general but we present two subclasses that are learnable, the second one being identi?able in polynomial time.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2006, 356 (1-2), pp.212-223
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536545
Contributeur : Aurélien Lemay <>
Soumis le : mardi 16 novembre 2010 - 13:53:07
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 15:47:09

Fichier

Identification-of-biRFSA-langu...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536545, version 1

Collections

Citation

Michel Latteux, Aurélien Lemay, Yves Roos, Alain Terlutte. Identification of biRFSA languages. Theoretical Computer Science, Elsevier, 2006, 356 (1-2), pp.212-223. 〈inria-00536545〉

Partager

Métriques

Consultations de la notice

195

Téléchargements de fichiers

134