Data processing: speech signal processing – linguistics – language – Linguistics – Natural language
Reexamination Certificate
2008-06-06
2011-11-01
Cyr, Leonard Saint (Department: 2626)
Data processing: speech signal processing, linguistics, language
Linguistics
Natural language
C704S007000, C704S008000, C704S010000
Reexamination Certificate
active
08050908
ABSTRACT:
A context-free grammar can be represented by a weighted finite-state transducer. This representation can be used to efficiently compile that grammar into a weighted finite-state automaton that accepts the strings allowed by the grammar with the corresponding weights. The rules of a context-free grammar are input. A finite-state automaton is generated from the input rules. Strongly connected components of the finite-state automaton are identified. An automaton is generated for each strongly connected component. A topology that defines a number of states, and that uses active ones of the non-terminal symbols of the context-free grammar as the labels between those states, is defined. The topology is expanded by replacing a transition, and its beginning and end states, with the automaton that includes, as a state, the symbol used as the label on that transition. The topology can be fully expanded or dynamically expanded as required to recognize a particular input string.
REFERENCES:
patent: 5086472 (1992-02-01), Yoshida
patent: 5625554 (1997-04-01), Cutting et al.
patent: 5649215 (1997-07-01), Itoh
patent: 5719997 (1998-02-01), Brown et al.
patent: 5721939 (1998-02-01), Kaplan
patent: 6032111 (2000-02-01), Mohri
patent: 6243679 (2001-06-01), Mohri et al.
patent: 6587844 (2003-07-01), Mohri
patent: 6868383 (2005-03-01), Bangalore et al.
patent: 6944588 (2005-09-01), Kempe
patent: 7069215 (2006-06-01), Bangalore et al.
patent: 7149695 (2006-12-01), Bellegarda
patent: 2003/0009331 (2003-01-01), Schalkwyk et al.
patent: 2003/0074184 (2003-04-01), Hayosh et al.
patent: 2003/0120480 (2003-06-01), Mohri et al.
patent: 2004/0176945 (2004-09-01), Inagaki et al.
Mohri et al. “Dynamic Compilation of Weighted Context-Free Grammars,” Proceedings of ACL '98. Montreal, Quebec, Canada, pp. 891-897.
Cortes et al., “Context-Free Recognition with Weighted Automata,” Jan. 2000, Kluwer Academic Publishers, vol. 3, No. 2-3, pp. 133-150.
Roche, Emmanual, Factorization of Finite-State Transducers, Mitsubishi Electric Research Laboratories, TR-95-2, Version 1.0, Feb. 1995, pp. 113.
Roche et al., Introduction, Finite-State Language Processing, MIT Press; Cambridge, MA, USA, pp. 1-66, Jun. 1997.
Karttunen, Lauri, “Finite-State Lexicon Compiler”, Xerox Palo Alto Research Center, Apr. 1993.
Knight et al., “A Primer on Finite-State Software for Natural Language Processing,” Aug. 1999, ten pages.
Mohri, M et al., “Weighted finite-state transducers in speech recognition,” Computer Speech and Language, Jan. 2002, pp. 69-88, vol. 16, No. 1, XP004418697, Elsevier, London, GB.
Mohri et al. “Regular approximation of context-free grammars through transformation,” Robustness in Language and Speech Technology, Kluwer Academic Press, The Netherlands, 2000, pp. 251-261.
Nederhof, M. “Context-free parsing through regular approximation,” Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, Ankara, Turkey, 1998, pp. 13-24.
Nederhof, M. “Regular approximations of CFLs: A grammatical view,” Proceedings of the International Workshop on Parsing Technologies, Massachusetts Institute of Technology, 1997, pp. 159-170.
Nederhof, M. “Practical experiments with regular approximation of context-free languages,” Association for Computational Linguistics, vol. 26, No. 1, 2000.
Mohri et al., “Weighted Grammar Tools: the GRM Library”, Robustness in Language and Speech Technology, Kluwer Academic Publishers, 2000, pp. 19-40.
Mohri Mehryar
Nederhof Mark-Jan
AT&T Intellectual Property II L.P.
Cyr Leonard Saint
LandOfFree
Systems and methods for generating weighted finite-state... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for generating weighted finite-state..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for generating weighted finite-state... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4255372