Opened 8 years ago
Closed 8 years ago
#16061 closed enhancement (fixed)
New method intersection (for automata and transducers) and new behavior of cartesian_product for transducers
| Reported by: | skropf | Owned by: | |
|---|---|---|---|
| Priority: | major | Milestone: | sage-6.2 |
| Component: | combinatorics | Keywords: | finite_state_machine |
| Cc: | dkrenn, cheuberg, slabbe | Merged in: | |
| Authors: | Sara Kropf | Reviewers: | Daniel Krenn |
| Report Upstream: | N/A | Work issues: | |
| Branch: | 7633cac (Commits, GitHub, GitLab) | Commit: | 7633cacfb8a13dc5fc808a947e7f4db3e1bd9ef8 |
| Dependencies: | #16016 | Stopgaps: |
Status badges
Description
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.
Change History (3)
comment:1 Changed 8 years ago by
- Branch set to u/skropf/fsm/cartesian-product-intersection
- Cc slabbe added
- Commit set to 7633cacfb8a13dc5fc808a947e7f4db3e1bd9ef8
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Reviewers set to Daniel Krenn
- Status changed from needs_review to positive_review
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.
comment:3 Changed 8 years ago by
- Branch changed from u/skropf/fsm/cartesian-product-intersection to 7633cacfb8a13dc5fc808a947e7f4db3e1bd9ef8
- Resolution set to fixed
- Status changed from positive_review to closed
Last 10 new commits:
Corrected docstring of intersection and cartesian_productTransducer.cartesian_product: replaced FSMEmptyWordSymbol by NoneAutomaton.intersection: docstring remove_epsilon_transition correctedMerge branch 'fsm/cartesian-product-intersection' of https://www.math.aau.at/git/sage into fsm/cartesian-product-intersectionimproved docstrings: linked methodsTransducer.cartesian_product: one example added with transducer and automatonTransducer.cartesian_product: ticket number for deprecation warning correctedMinor changes: docstring, indentationcorrected one whitespace errorTransducer.cartesian_product: small correction in docstring