Data processing: speech signal processing – linguistics – language – Linguistics – Natural language
Reexamination Certificate
2005-11-01
2005-11-01
{hacek over (S)}mits, Tālivaldis Ivars (Department: 2654)
Data processing: speech signal processing, linguistics, language
Linguistics
Natural language
C704S257000
Reexamination Certificate
active
06961693
ABSTRACT:
A method factors an ambiguous finite state transducer (FST) into two finite state transducers. The first FST is functional (i.e., unambiguous). The second FST retains the ambiguity of the original FST but is fail-safe (i.e., no failing paths) when applied to the output of the first FST. That is, the application of the second FST to an input string never leads to a state that does not provide a transition for the next symbol in the input. Subsequently, the first FST can be factorized into a left-sequential FST and a right-sequential FST that jointly represent a bi-machine.
REFERENCES:
patent: 6278973 (2001-08-01), Chung et al.
patent: WO 9901828 (1999-01-01), None
Kshirasagar Naik, Efficient Computation of Unique Input/Output Sequences in Finite-State Machines, Aug. 1997, IEEE/ACM Transactions On Networking, vol. 5, No. 4.
Monteiro et al., Finite State Machine Decomposition for Low Power, Jun. 15-19, 1998, Design Automation Conference, pp.: 758-763.
Emmanuel Roche, Factorization of Finite-State Transducers, Feb. 1995, Mitsubishi Electric Research Laboratories Cambridge Research Center.
Kukula et al., Finite Sate Machine Decomposition By Transition Pairing , Nov. 11-14, 1991, International Conference on Computer-Aided Design, pp.: 414-417.
Pereira et al. Finite-state approximation of phrase structure grammars, 1991, Proceedings of the 29th conference on Association for Computational Linguistics, pp 246-255.
Elgot C.C et al. “On Relations Defined by Generalized Finite Automata,” IBM Journal of Research and Development, pp. 47-68, Jan., 1965.
Kempe, Andre “Reduction of Intermediate Alphabets in Finite-State Transducer Cascades,” 7thConference on Automatic Natural Language Processing (TALN), Lausanne, Switzerland; Sep. 16-18, 2000.
Kempe, Andre “Factorization of Ambiguous Finite-State Transducers,” Pre-Proceedings of the 5thInternational Conference on Implementation and Application of Automata (CIAA), p. 157-164, London, Ontario, Canada, Jul. 2000. Final Proceedings in: Springer-Verlag Lecture Notes in Computer Science.
Roche E. et al. “Introduction”, Finite-State Language Processing, MIT Press, Cambridge, MA, USA, pp. 1-66, Jun. 1997.
Sakarovitch, Jacques “A Construction on Finite Automata that has Remained Hidden” Theoretical Computer Science, 204:205-231, Sep. 1998.
Schutzenberger, Marcel Paul “A Remark on Finite Transducers,” Information and Control, 4: 185-187, Sep. 1961.
Shortledge Thomas E
{hacek over (S)}mits Tälivaldis Ivars
LandOfFree
Method and apparatus for factoring ambiguous 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 Method and apparatus for factoring ambiguous finite state..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for factoring ambiguous finite state... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3468258