Method and apparatus for factoring unambiguous finite state...

Details Method and apparatus for factoring unambiguous finite state... Method and apparatus for factoring unambiguous finite state...

2005-09-13

2005-09-13

Smits, Talivaldis Ivars (Department: 2654)

Data processing: speech signal processing, linguistics, language

Linguistics

Natural language

C704S257000

Reexamination Certificate

active

06944588

ABSTRACT:
A method factors a functional (i.e., ambiguous) finite state transducer (FST) into a bimachine with a reduced intermediate alphabet. Initially, the method determines an emission matrix corresponding to a factorization of the functional FST. Subsequently, the emission matrix is split into a plurality of emission sub-matrices equal in number to the number of input symbols to reduce the intermediate alphabet. Equal rows of each emission sub-matrix are assigned an identical index value in its corresponding factorization matrix before creating the bimachine.

REFERENCES:
patent: 6243679 (2001-06-01), Mohri et al.
patent: 6456971 (2002-09-01), Mohri et al.
patent: 2004/0133603 (2004-07-01), Chang et al.
Kukula, James et al., Finite State Machine Decomposition by Transition Pairing, 1991 IEEE ICCAD-91, Nov. 1991, 414-417.
Roche, Emmanual, Factorization of Finite-State Transducers, Mitsubishi Electrical Research Laboratories TR-95-2 Feb. 1995, 1-13.
Devadas, Srinivas et al., Decomposition and Factorization of Sequential Finite State Machines, IEEE Transactions on Computer-Aided Design, Nov. 1989, 1206-1217.
Kempe, Andre et al., Parallel replacement in finite state calculus, Association for Computational Linguistcs,Aug. 1996, pp. 622-627.
Kempe, Andre, Finite state transducers approximating Hidden Markov Models, Association for Computational Linguistics, Jul. 1997, pp. 460-467.
Elgot C.C et al., “On Relations Defined by Generalized Finite Automata,” IBM Journal of Research and Development, pp. 47-68, 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, 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, 1997.
Sakarovitch, Jacques “A Construction of Finite Automata that has Remained Hidden,” Theoretical Computer Science, 204:205-231, 1998.
Schutzenberger, Marcel Paul “A Remark on Finite Transducers,” Information and Control, 4: 185-187, 1961.

Affiliated with

Also associated with

Rating

Method and apparatus for factoring unambiguous 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 unambiguous 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 unambiguous finite state... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3430026