Difference: MpdtExtension (8 vs. 9)

Revision 92015-10-29 - RichardSproat

Line: 1 to 1
 
META TOPICPARENT name="FstExtensions"

Multi-Pushdown Transducer Library (MPDTs)

Line: 6 to 6
 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.

configure include
Changed:
<
<
--enable-mpdt <fst/extensions/mpdt/mpdtlib.h>
>
>
--enable-mpdt (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 1-based enumeration) of each pair
Line: 21 to 21
 
  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    
Changed:
<
<
Expand Expand(a_mpdt, parens, assignments, &b_fst); expands a (bounded-stack) MPDT as an FST Time, Space: O(e(V + E)) for the default 2-stack read-restrict configuration
>
>
Expand Expand(a_mpdt, parens, assignments, &b_fst); expands a (bounded-stack) MPDT as an FST Time, Space: O(eO(V + E)) for the default 2-stack read-restrict 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)
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback