Data processing: speech signal processing – linguistics – language – Linguistics
Reexamination Certificate
2007-02-20
2007-02-20
{hacek over (S)}mits, Talivaldis Ivars (Department: 2626)
Data processing: speech signal processing, linguistics, language
Linguistics
Reexamination Certificate
active
10199220
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: 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: 6944588 (2005-09-01), Kempe
patent: 2003/0009331 (2003-01-01), Schalkwyk 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 Publisher, vol. 3, No. 2-3, pp. 133-150.
Roche, Emmanual, Factorization of Finite-State Transducers, Mitsubishi Electrical Research Laboratories, TR-95-2, Version 1.0, Feb. 1995, pp. 1-13.
Roche, et al. “Introlduction,” Finite-State Language Processing, MIT Press, Cambridge, MA, USA, pp. 1-66, Jun. 1997.
Lauri Karttunen, “Finite-State Lexicon Compiler”, Xerox Palo Alto Research Center, Apr. 1993.
Mohri et al., “Regular approximation of context-free grammars through transformation”, Robustness in Language and Speech Technology, Kluwer Academic Press, The Nethaldns, 2000, pp. 251-261.
Nederhof, M., “Context-free parsing through regular approximation”. Proceedings of the National Workshop on Finite State Methods in Natural Language Processing, Ankara, Turkey, 1997, pp. 13-24.
Nederhof, M., “Regular approximations of CFLs: A grammatical view,” Proceedings of the National 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.
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 Mehryar
Nederhof Mark-Jan
AT&T Corp.
Ng Eunice
{hacek over (S)}mits Talivaldis Ivars
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-3853678