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);
template <class Arc> IntersectFst<Arc>:: IntersectFst(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2);
fstintersect [--opts] a.fsa b.fsa out.fsa --connect: Trim output (def: true)

Examples

A:

B:

A ∩ B:

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

Complexity

Same as Compose.

Caveats

Same as Compose.

See Also

Composition Filters, Matchers, State Tables

-- MichaelRiley - 30 Jun 2007