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

sagemath / sage

Main repository of SageMath

https://www.sagemath.org

Other

1.37k stars 469 forks source link

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

Closed c50b3d32-6cb1-4b90-a060-6a332e54ef6a closed 10 years ago

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 10 years ago

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

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 10 years ago

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`

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 10 years ago

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

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 10 years ago

Commit: 7633cac

dkrenn commented 10 years ago

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 commented 10 years ago

Reviewer: Daniel Krenn

vbraun commented 10 years ago

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