
META TOPICPARENT 
name="FstExtensions" 
MultiPushdown Transducer Library (MPDTs) 
 for multiple stacks. As with the PDT extension, an MPDT is encoded as an FST where some transitions are labeled with open or close parentheses, with each mated pair of parentheses being assigned to one of the stacks. To be interpreted as an MPDT, parentheses within a stack must balance on a path.


< < 
enablempdt 
<fst/extensions/mpdt/mpdtlib.h> 

> > 
enablempdt 
(coming soon) <fst/extensions/mpdt/mpdtlib.h> 


An MPDT is encoded as an FST where some transitions are labeled with open or close parentheses, with each mated pair of parentheses being assigned to one of the stacks. To be interpreted as an MPDT, parentheses within a stack must balance on a path. The subset of the transducer labels that correspond to parenthesis (open, closed) pairs is designated from the C++library in a vector<pair<Label, Label>> , and the assignments are given as a correponding
vector<typename Arc::Label> . From the command line the parentheses and assignments are passed from a file of lines of label pairs, with a third column showing the stack affiliation (in a 1based enumeration) of each pair 


Compose(a_fst, b_mpdt, parens, assignments, &c_mpdt); 



mpdtcompose mpdt_parentheses=mpdt.parens a.mpdt b.fst >c.mpdt 



mpdtcompose mpdt_parentheses=mpdt.parens left_mpdt=false a.fst b.mpdt >c.mpdt 




< < 
Expand 
Expand(a_mpdt, parens, assignments, &b_fst); 
expands a (boundedstack) MPDT as an FST 
Time, Space: O(e^{(V + E)}) for the default 2stack readrestrict configuration 

> > 
Expand 
Expand(a_mpdt, parens, assignments, &b_fst); 
expands a (boundedstack) MPDT as an FST 
Time, Space: O(e^{O(V + E)}) for the default 2stack readrestrict configuration 



mpdtexpand mpdt_parentheses=mpdt.parens a.mpdt >b.fst 


Info 
mpdtinfo mpdt_parentheses=mpdt.parens a.mpdt 
prints out information about an MPDT 

Reverse 
Reverse(a_mpdt, parens, &b_mpdt); 
reverses an MPDT; also reverses the stack assignments 
Time, Space: O(V + E) 
