WFSC   —   XEROX'S WEIGHTED FINITE-STATE COMPILER

WFSC compiles regular expressions into multi-tape weighted finite-state machines (n-WFSMs) with symbol classes. These machines define regular (also called rational) n-ary relations which assign a weight from some semiring to any n-tuple of strings (0 if the n-tuple is not accepted). Special cases of n-WFSMs are weighted acceptors (n=1) and weighted transducers (n=2).
The n-WFSMs can be displayed, saved to files, and transformed or merged by various algorithms that can be accessed through an end user interface or an API.

DEMO :

Under construction.

ALGORITHMS :

WFSC provides a large number of algorithms such as determinisation, minimisation, pruning, concatenation, Kleene-star, Kleene-plus, union, intersection, composition, cross-product, multi-tape join, projection, and many more.

AUTHORS :

WFSC was created within the Finite State Technology group
by Christof Baeijs, Tibor Csáki, Tamás Gaál, Franck Guingne, André Kempe, Florent Nicart, and Ivan Thomas,
occasionally collaborating with Kenneth Beesley (XRCE), Jean-Marc Champarnaud (Univ. Rouen, France), and Lauri Karttunen (Palo Alto Research Center, CA, USA).

PUBLICATIONS :

WFSC was described as a whole first in

André Kempe, Christof Baeijs, Tamás Gaál, Franck Guingne, and Florent Nicart. 2003. WFSC - A new weighted finite state compiler. In O.H. Ibarra and Z. Dang, editors, Proc. 8th Int. Conf. on Implementation and Application of Automata (CIAA'03), volume 2759 of Lecture Notes in Computer Science, pages 108-119, Santa Barbara, CA, USA. Springer Verlag.

WFSC's algorithms for n-WFSMs follow the principles described in

	André Kempe, Jean-Marc Champarnaud, and Jason Eisner. 2004. A note on join and auto-intersection of n-ary rational relations. In B. Watson and L. Cleophas, editors, Proc. Eindhoven FASTAR Days, Eindhoven, Netherlands.
	André Kempe, Jean-Marc Champarnaud, Jason Eisner, Franck Guingne, and Florent Nicart. 2005. A class of rational n-WFSM auto-intersections. In J. Farré, I. Litovski, and S. Schmitz, editors, Proc. 10th Int. Conf. on Implementation and Application of Automata (CIAA'05), pages 266-274, Sophia Antipolis, France.
	André Kempe, Jean-Marc Champarnaud, Franck Guingne, and Florent Nicart. 2005. WFSM auto-intersection and join algorithms. In Proc. 5th Int. Workshop on Finite-State Methods and Natural Language Processing (FSMNLP'05), Helsinki, Finland.