New method intersection (for automata and transducers) and new behavior of cartesian_product for transducers

[sagetrac-skropf]

Intersection now constructs the automaton (or transducer) which accepts (computes) the intersection
of the languages of the given automata (transducers). This was earlier done by cartesian_product. A given input is accepted if it was accepted by both given finite state machines. Furthermore, for transducers, the output has to be same in both given transducer. Furthermore, transitions with empty input (or output, for transducers) are not allowed.

For an automaton, cartesian_product does the same as intersection. But for transducers, it
returns a transducer which computes the pairs of output labels of the given transducer with a given input.
Thus, the output sequences of both given transducers for a given input are combined into a sequence of pairs of outputlabels.

A deprecation warning is given when Transducer.cartesian_product is called as the output has changed substantially.

Depends on #16016

CC: @dkrenn @cheuberg @seblabbe

Component: combinatorics

Author: Sara Kropf

Branch/Commit: 7633cac

Reviewer: Daniel Krenn

Issue created by migration from https://trac.sagemath.org/ticket/16061

[sagetrac-skropf]

Last 10 new commits:

bb59856	Corrected docstring of intersection and cartesian_product
a5cf1c7	Transducer.cartesian_product: replaced FSMEmptyWordSymbol by None
30cba42	Automaton.intersection: docstring remove_epsilon_transition corrected
4e26b52	Merge branch 'fsm/cartesian-product-intersection' of https://www.math.aau.at/git/sage into fsm/cartesian-product-intersection
d0f8287	improved docstrings: linked methods
29fd372	Transducer.cartesian_product: one example added with transducer and automaton
f37a4d3	Transducer.cartesian_product: ticket number for deprecation warning corrected
1e310b0	Minor changes: docstring, indentation
83b0341	corrected one whitespace error
7633cac	Transducer.cartesian_product: small correction in docstring

[sagetrac-skropf]

Branch: u/skropf/fsm/cartesian-product-intersection

[sagetrac-skropf]

Commit: 7633cac

[dkrenn]

comment:2

summary:

• I've reviewed, doctests pass, documentation looks fine
• I made a couple of minor changes; those were cross-reviewed by the authors
• my suggested improvements were included; I've reviewed those
• it merges on 6.2.beta7

Therefore, this is a positive review for me.

[dkrenn]

Reviewer: Daniel Krenn

[vbraun]

Changed branch from u/skropf/fsm/cartesian-product-intersection to 7633cac