Data processing: speech signal processing – linguistics – language – Linguistics – Natural language
Reexamination Certificate
2007-10-30
2007-10-30
Hudspeth, David (Department: 2626)
Data processing: speech signal processing, linguistics, language
Linguistics
Natural language
C704S001000, C704S243000
Reexamination Certificate
active
10199227
ABSTRACT:
Context-free grammars generally comprise a large number of rules, where each rule defines how a sting of symbols is generated from a different series of symbols. While techniques for creating finite-state automata from the rules of context-free grammars exist, these techniques require an input grammar to be strongly regular. Systems and methods that convert the rules of a context-free grammar into a strongly regular grammar include transforming each input rule into a set of output rules that approximate the input rule. The output rules are all right- or left-linear and are strongly regular. In various exemplary embodiments, the output rules are output in a specific format that specifies, for each rule, the left-hand non-terminal symbol, a single right-hand non-terminal symbol, and zero, one or more terminal symbols. If the input context-free grammar rule is weighted, the weight of that rule is distributed and assigned to the output rules.
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
patent: 6587844 (2003-07-01), Mohri
patent: 6944588 (2005-09-01), Kempe
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. “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. Dynamic Compilation of Weighted Contest-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 Electrical 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.
AT&T Corp.
Hudspeth David
Ng Eunice
LandOfFree
Systems and methods for regularly approximating context-free... 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 regularly approximating context-free..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for regularly approximating context-free... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3838131