Finite Eilenberg Machines

Benoit Razet 1
1 SANSKRIT - Sanskrit Computational Linguistics
Inria Paris-Rocquencourt, Université d'Hyderabad
Abstract : Eilenberg machines define a general computational model. They are well suited to the simulation of problems specified using finite state formalisms such as formal languages and automata theory. This paper introduces a subclass of them called finite Eilenberg machines. We give a formal description of complete and efficient algorithms which permit the simulation of such machines. We show that our finiteness restriction ensures a correct behavior of the simulation. Interpretations of this restriction are studied for the particular cases of non-deterministic automata (NFA) and rational transducers, leading to applications to computational linguistics. The given implementation provides a generic simulation procedure for any problem encoded as a composition of finite Eilenberg machines.
Type de document :
Rapport
[Research Report] INRIA. 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00257354
Contributeur : Benoit Razet <>
Soumis le : vendredi 4 avril 2008 - 09:40:11
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : lundi 22 octobre 2012 - 12:55:50

Fichiers

fem.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00257354, version 3

Collections

Citation

Benoit Razet. Finite Eilenberg Machines. [Research Report] INRIA. 2008. 〈inria-00257354v3〉

Partager

Métriques

Consultations de la notice

102

Téléchargements de fichiers

107