×

zbMATH — the first resource for mathematics

Pseudo-minimal transducer. (English) Zbl 0951.68063
Summary: The algorithm that we present here builds an acyclic deterministic finite state machine (automaton or transducer), as each word recognized has a proper element, i.e. a transition or a final state that belongs only to the recognizing path of this word.

MSC:
68Q45 Formal languages and automata
68T50 Natural language processing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. Gross, D. Perrin, Electronic Dictionnaries and Automata in Computational Linguistics, Lecture Notes in Computer Science, vol. 377, Springer, Berlin, 1989.
[2] Hopcroft Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, MA, 1979. · Zbl 0426.68001
[3] D. Maurel, Building automaton on Schemata and Acceptability Tables, Lecture Notes in Computer Science, vol. 1260, Springer, Berlin, 1997, pp. 72-86.
[4] D. Maurel, C. Belleil, E. Eggert, O. Piton, Le projet PROLEX, séminaire Représentations et Outils pour les Bases Lexicales, Morphologie Robuste de l’action Lexique du GDR-PRC CHM, Grenoble, 1996.
[5] Maurel, D.; Belleil, C.; Piton, O.; Eggert, E., Un dictionnaire électronique relationnel pour LES noms propres, Revue française de linguistique appliquée, 2-1, 101-111, (1997)
[6] M. Mohri, Minimization of Sequential Transducers, Lecture Notes in Computer Science, Springer, Berlin, 1994a, p. 807. · Zbl 0944.68091
[7] Mohri, M., Finite-state transducers in language and speech processing, Comput. linguistics, 23-2, 269-311, (1997)
[8] D. Revuz, Dictionnaries et lexiques - Méthodes et algorithmes, Doctoral dissertation in Computer Science, University of Paris, VII, 1991.
[9] E. Roche, Y. Schabes (Eds.), Finite State Language Processing, MIT Press, Cambridge, MA, 1997.
[10] B.W. Watson, Taxonomies and Toolkits of Regular Language Algorithms, Thesis, Technische Universiteit Eindhoven, 1995. · Zbl 0832.68064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.