Intersect

Description

This operation computes the intersection (Hadamard product) of two FSAs. Only strings that are in both automata are retained in the result.

The two arguments must be acceptors. One of the arguments must be label-sorted (or otherwise support an appropriate matcher).The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight for instance).

Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behaviour used by intersection.

Usage

template <class Arc> 
void Intersect(const Fst<Arc> &ifsa1, const Fst<Arc> &ifsa2, MutableFst<Arc> *ofsa);
doc
template <class Arc> IntersectFst<Arc>::
IntersectFst(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2);
doc
fstintersect [--opts] a.fsa b.fsa out.fsa
  --connect: Trim output (def: true)
 

Examples

A:

intersect1.jpg

B:

intersect2.jpg

A ∩ B:

intersect3.jpg

Intersect(A, B, &C);
IntersectFst<Arc>(A, B);
fstintersect a.fsa b.fsa out.fsa

Complexity

Same as Compose.

Caveats

Same as Compose.

-- MichaelRiley - 30 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg intersect1.jpg r3 r2 r1 manage 11.0 K 2007-06-30 - 21:59 MichaelRiley  
JPEGjpg intersect2.jpg r2 r1 manage 10.4 K 2007-06-30 - 21:59 MichaelRiley  
JPEGjpg intersect3.jpg r2 r1 manage 13.9 K 2007-06-30 - 22:00 MichaelRiley  
Topic revision: r6 - 2011-12-06 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2014 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback