Opened 8 years ago
Closed 8 years ago
#16255 closed enhancement (fixed)
FiniteStateMachine.with_final_word_out: New method
Reported by:  cheuberg  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  finite_state_machine 
Cc:  skropf  Merged in:  
Authors:  Clemens Heuberger, Daniel Krenn  Reviewers:  Daniel Krenn, Sara Kropf 
Report Upstream:  N/A  Work issues:  
Branch:  7db5774 (Commits, GitHub, GitLab)  Commit:  7db57742c744f66ae944ea22231a55c9ca498514 
Dependencies:  #16145, #16206, #16207, #16253  Stopgaps: 
Description (last modified by )
Constructs a finite state machine with final output words for all states by implicitly reading trailing letters until a final state is reached. This is e.g. useful for finite state machines operating on digit expansions: there, it is sometimes required to read a sufficient number of trailing zeros (at the most significant positions) in order to reach a final state and to flush all carries. In this case, this method constructs an essentially equivalent finite state machine in the sense that it not longer requires adding sufficiently many trailing zeros. However, it is the responsibility of the user to make sure that if adding trailing zeros to the input anyway, the output is equivalent.
Change History (14)
comment:1 Changed 8 years ago by
 Branch set to u/cheuberg/fsm/with_final_word_out
 Commit set to 2c11f6a0024ee6c7a663ea687c9d44c6b987b348
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
 Branch changed from u/cheuberg/fsm/with_final_word_out to u/dkrenn/fsm/with_final_word_out
comment:3 Changed 8 years ago by
 Cc dkrenn removed
 Commit changed from 2c11f6a0024ee6c7a663ea687c9d44c6b987b348 to fe32df836177f9eadf140014160701b503b7c6aa
 Reviewers set to Daniel Krenn
I've did a very careful reviewing. Everything was fine. I decided to extend its functionality. Please review those changes.
New commits:
fe32df8  extending functionality of with_final_word_out and inplaceversion

comment:4 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:5 Changed 8 years ago by
 Branch changed from u/dkrenn/fsm/with_final_word_out to u/skropf/fsm/with_final_word_out
comment:6 Changed 8 years ago by
 Branch changed from u/skropf/fsm/with_final_word_out to u/cheuberg/fsm/with_final_word_out
comment:7 Changed 8 years ago by
 Commit changed from fe32df836177f9eadf140014160701b503b7c6aa to 1382dec088477ed314f206715e83a844690b2c2c
Last 10 new commits:
21392c5  added doctests to FSMState.deepcopy to check that deepcopy of a property works

696f66e  FiniteStateMachine.with_final_word_out: New method

c15e3d8  Small changes in the documentation of with_final_word_out

0312268  line break in docstring

e0963c4  FiniteStateMachine.with_final_word_out: replace "loop" by "cycle"

2c11f6a  FiniteStateMachine.with_final_word_out: only support transitions with input labels of length 1

fe32df8  extending functionality of with_final_word_out and inplaceversion

134fd7e  Added explanations in documentation of Transducer.with_final_word_out

b9bfd58  renamed parameter allow_not_accepting to allow_non_final; docstring improvements

1382dec  Rewrote with_final_output to cache all intermediate results.

comment:8 Changed 8 years ago by
I rewrote some docstrings, then I rewrote
fe32df8  extending functionality of with_final_word_out and inplaceversion

so that all intermediate results are cached. Please review.
comment:9 Changed 8 years ago by
 Commit changed from 1382dec088477ed314f206715e83a844690b2c2c to a466e625f539a576b9790e7022bb6373f05fb1cc
Branch pushed to git repo; I updated commit sha1. New commits:
a466e62  FiniteStateMachine.__init__: allow with_final_word_out=0

comment:10 Changed 8 years ago by
 Commit changed from a466e625f539a576b9790e7022bb6373f05fb1cc to 5135618522e478115b5e0d342f08cf0bbbbe4fa0
Branch pushed to git repo; I updated commit sha1. New commits:
5135618  trac #16255: add doctest for last commit

comment:11 Changed 8 years ago by
 Branch changed from u/cheuberg/fsm/with_final_word_out to u/skropf/fsm/with_final_word_out
 Commit changed from 5135618522e478115b5e0d342f08cf0bbbbe4fa0 to 5ca61d1e7360dfb54b4b65605e7be4f125734dae
 Reviewers changed from Daniel Krenn to Daniel Krenn, Sara Kropf
I added a doctest and a comment to clarify that final states with empty final output are considered in the right way.
New commits:
5ca61d1  FiniteStateMachine.construct_final_word_out: clarified difference between None and empty list

comment:12 Changed 8 years ago by
 Branch changed from u/skropf/fsm/with_final_word_out to u/dkrenn/fsm/with_final_word_out
comment:13 Changed 8 years ago by
 Commit changed from 5ca61d1e7360dfb54b4b65605e7be4f125734dae to 7db57742c744f66ae944ea22231a55c9ca498514
 Status changed from needs_review to positive_review
Reviewed the changes. Everything looks fine now.
New commits:
7db5774  added spaces after commentsymbol in code

comment:14 Changed 8 years ago by
 Branch changed from u/dkrenn/fsm/with_final_word_out to 7db57742c744f66ae944ea22231a55c9ca498514
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
Deleted a check for consistency in _latex_
reworded ValueError (joined sentences)
reviewer patch: line breaks in documentation
reworded two docstrings
added doctests to FSMState.deepcopy to check that deepcopy of a property works
FiniteStateMachine.with_final_word_out: New method
Small changes in the documentation of with_final_word_out
line break in docstring
FiniteStateMachine.with_final_word_out: replace "loop" by "cycle"
FiniteStateMachine.with_final_word_out: only support transitions with input labels of length 1