Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines

Details Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines

2011-04-28

arxiv.org/abs/1104.5362v2

Proc. FSMNLP 2009, Pretoria, South Africa. July 21-24. (invited talk)

Computer Science

Formal Languages and Automata Theory

15 pages, 7 figures, LaTeX (+ .eps)

Scientific paper

A weighted finite-state machine with n tapes (n-WFSM) defines a rational relation on n strings. It is a generalization of weighted acceptors (one tape) and transducers (two tapes). After recalling some basic definitions about n-ary weighted rational relations and n-WFSMs, we summarize some central operations on these relations and machines, such as join and auto-intersection. Unfortunately, due to Post's Correspondence Problem, a fully general join or auto-intersection algorithm cannot exist. We recall a restricted algorithm for a class of n-WFSMs. Through a series of practical applications, we finally investigate the augmented descriptive power of n-WFSMs and their join, compared to classical transducers and their composition. Some applications are not feasible with the latter. The series includes: the morphological analysis of Semitic languages, the preservation of intermediate results in transducer cascades, the induction of morphological rules from corpora, the alignment of lexicon entries, the automatic extraction of acronyms and their meaning from corpora, and the search for cognates in a bilingual lexicon. All described operations and applications have been implemented with Xerox's WFSC tool.

Affiliated with

Also associated with

No associations

Rating

Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-449571