Opened 8 years ago

Closed 8 years ago

#16254 closed enhancement (fixed)

FiniteStateMachine: final_word_out: more implementations

Reported by: skropf Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorics Keywords: finite_state_machine
Cc: dkrenn, cheuberg Merged in:
Authors: Sara Kropf, Clemens Heuberger Reviewers: Clemens Heuberger, Daniel Krenn
Report Upstream: N/A Work issues:
Branch: 322991f (Commits, GitHub, GitLab) Commit: 322991fca711579aabf13703d3531cfaab4cbe5b
Dependencies: #16206, #16207, #16253, #16145 Stopgaps:

Status badges


See also #16191.

final_word_out is used in subsequential transducers. A transducer is said to be subsequential if it is deterministic, every state is final and it has a final output word for each final state, i.e., when reading an input and reaching some final state along some path, then the final output word of this state is appended to the output labels collected along the path.

This will facilitate various transducers, e.g., when we currently have to read a sufficiently large number of zeros in order to flush some more output.

In the following functions, final_word_out is now implemented:

  • FiniteStateMachine.composition: If the output of one finite state machine is used as input of another one, then also the final output word of the first one is fed into the second one.
  • FiniteStateMachine.output_projection: If the automaton which recognizes the output of a transducer is constructed, then the final output word has to be the last part of a recognized input. This is implemented by constructing a new final state and adding one transition for each final output word of the original transducer. The original final states are not final anymore.
  • FiniteStateMachine.prepone_output: Here, final output words have to be considered like any other transition leaving a state.
  • FiniteStateMachine.product_FiniteStateMachine: A function which handles the combination of final output words is required if there exists non-trivial final output words.
  • Transducer.cartesian_product: The final output words of the new transducer consists of pairs of final output words of the original transducers.

Change History (8)

comment:1 Changed 8 years ago by cheuberg

  • Summary changed from final_word_out: more implementations to FiniteStateMachine: final_word_out: more implementations

comment:2 Changed 8 years ago by skropf

  • Branch set to u/skropf/fsm/final_output_implemented
  • Commit set to c261805b584f8bc11c12adacd8050af1f3db37b2
  • Dependencies changed from #16206, #16207, #16253 to #16206, #16207, #16253, #16145
  • Status changed from new to needs_review

comment:3 Changed 8 years ago by cheuberg

  • Authors changed from Sara Kropf to Sara Kropf, Clemens Heuberger
  • Reviewers set to Clemens Heuberger

I reviewed this earlier and added a few commits. Most of them minor, but I rewrote parts of Transducer.cartesian_product and changed the default for final_function in FiniteStateMachine.product_FiniteStateMachine.

  • fd09b66 Minor changes in docstring
  • 3dd943d Code cleanup in prepone_output
  • ca6ae02 FiniteStateMachine.projection: store doubly used list.
  • a042f3a FiniteStateMachine.product_FiniteStateMachine: changed default for final_function
  • 867a804 FiniteStateMachine.product_FiniteStateMachine: minor docstring edits
  • 130bec2 FiniteStateMachine.product_FiniteStateMachine: simplify code
  • 098473d Transducer.cartesian_product: use itertools.izip_longest
  • 74e4c05 FiniteStateMachine.composition: modified docstring
  • 6e9ad7b FiniteStateMachine._composition_direct: states -> iter_states
  • ea63af0 FiniteStateMachine._composition_direct: provide final_function

comment:4 Changed 8 years ago by dkrenn

  • Branch changed from u/skropf/fsm/final_output_implemented to u/dkrenn/fsm/final_output_implemented

comment:5 Changed 8 years ago by dkrenn

  • Commit changed from c261805b584f8bc11c12adacd8050af1f3db37b2 to 322991fca711579aabf13703d3531cfaab4cbe5b
  • Reviewers changed from Clemens Heuberger to Clemens Heuberger, Daniel Krenn

made some minor changes; please cross-review. Apart from those, this is a positive review for me, so mark it whenever you like.

New commits:

322991fa couple of minor changes during review

comment:6 Changed 8 years ago by skropf

  • Status changed from needs_review to positive_review

All changes are fine for me. Thus, I mark it as positive_review, as suggested.

comment:7 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 8 years ago by vbraun

  • Branch changed from u/dkrenn/fsm/final_output_implemented to 322991fca711579aabf13703d3531cfaab4cbe5b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.