Opened 8 years ago
Closed 8 years ago
#16538 closed defect (fixed)
FiniteStateMachine.process: follow all paths if machine is nondeterministic
Reported by:  cheuberg  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  finite state machines  Keywords:  finite_state_machine 
Cc:  dkrenn, skropf  Merged in:  
Authors:  Daniel Krenn  Reviewers:  Clemens Heuberger, Sara Kropf 
Report Upstream:  N/A  Work issues:  
Branch:  b75665e (Commits, GitHub, GitLab)  Commit:  b75665ef08fbe657b5891f751eb7cce64ff81fd6 
Dependencies:  Stopgaps: 
Description (last modified by )
Prior to #16539, a (more or less) random path was chosen in case of ambiguity
in FiniteStateMachine.process
. In #16539, this undesired behaviour is replaced by a NonImplementedError
.
However, ideally, in the case of nondeterministic machines, all possible paths should be considered. This shall be implemented in this ticket.
Change History (21)
comment:1 Changed 8 years ago by
 Description modified (diff)
comment:2 Changed 8 years ago by
 Branch set to u/dkrenn/fsm/processiteratornondet
comment:3 Changed 8 years ago by
 Commit set to 51d35dc08fc621267d95919eb07bb5017bb653bd
 Description modified (diff)
 Status changed from new to needs_review
comment:4 Changed 8 years ago by
 Reviewers set to Clemens Heuberger
In an offline proccess, I reviewed several iterations of this rather large patch and contributed a few commits with small improvements. I believe that the patch does what it is supposed to do; doctests pass; documentation builds.
The documentation, in particular those of the high level methods .process
, .__call__
, .iter_process
, .epsilon_successors
and perhaps also of FSMProcessIterator
, FSMProcessIterator.__next__
and FSMProcessIterator.results
should be reviewed independently.
comment:5 Changed 8 years ago by
 Branch changed from u/dkrenn/fsm/processiteratornondet to u/cheuberg/fsm/processiteratornondet
comment:6 Changed 8 years ago by
 Commit changed from 51d35dc08fc621267d95919eb07bb5017bb653bd to 4bbf3a54b51896447d601e046aff372f398498c6
comment:7 Changed 8 years ago by
 Branch changed from u/cheuberg/fsm/processiteratornondet to u/dkrenn/fsm/processiteratornondet
comment:8 Changed 8 years ago by
 Commit changed from 4bbf3a54b51896447d601e046aff372f398498c6 to 4aee36f7ecadc6b04a6ba62ac4c5961d76249133
Clear "commit" field so that Daniel's new branch is actually used.
Last 10 new commits:
7e225f1  Merge remotetracking branch 'aau/fsm/codecleanuppost16067' into fsm/processiteratornondet

59d736b  again some small corrections in doctests (word_in transposition)

15d09a9  trac #16538: word of tuples (instead of word of lists), one more transposition

51d35dc  reworded docstring

1417c7d  trac #16538: correct overlooked renamed variable

4bbf3a5  trac #16538: correct second overlooked renamed variable

9250ad9  trac #16538: add parameter 'always_include_output' for compatibility

d5c8834  trac #16538: improve documentation of 'always_include_output'

275b653  included 'always_include_output' in _process_default_options_

4aee36f  description of always_include_output changed in Automaton.process

comment:9 Changed 8 years ago by
 Commit changed from 4aee36f7ecadc6b04a6ba62ac4c5961d76249133 to 7861454364d8d6aa62fbee79c7b03c84223e7f91
Branch pushed to git repo; I updated commit sha1. New commits:
e4829c3  FiniteStateMachine: Improvements of the documentation of __call__ and process

4bf7193  Merge branch 'fsm/processiteratornondet' of https://www.math.aau.at/git/sage into fsm/processiteratornondet

0218129  Finite State Machine: rearrangement of parameters explanation in process

1c442bc  Multitape FSM and transducer example in process

7c96f5c  Merge branch 'fsm/processiteratornondet' of https://www.math.aau.at/git/sage into fsm/processiteratornondet

1e31c86  Multitape automaton example

7861454  corrected typo and spacing in docstrings

comment:10 followup: ↓ 13 Changed 8 years ago by
 Reviewers changed from Clemens Heuberger to Clemens Heuberger, Sara Kropf
I improved parts of the documentation. Especially, those of the high level functions.
comment:11 Changed 8 years ago by
 Branch changed from u/dkrenn/fsm/processiteratornondet to u/cheuberg/fsm/processiteratornondet
comment:12 Changed 8 years ago by
 Commit changed from 7861454364d8d6aa62fbee79c7b03c84223e7f91 to 75e23d083a840ada2308678fc67a0f0eeda59aa9
comment:13 in reply to: ↑ 10 Changed 8 years ago by
Replying to skropf:
I improved parts of the documentation. Especially, those of the high level functions.
I reviewed your changes and pushed a few minor changes.
Following the discussion on sagedevel, the docstring of __call__
is now included into the reference manual.
comment:14 Changed 8 years ago by
 Branch changed from u/cheuberg/fsm/processiteratornondet to u/skropf/fsm/processiteratornondet
 Commit changed from 75e23d083a840ada2308678fc67a0f0eeda59aa9 to bcfbd2408c706f7f4062d765e9cbc8cef0aa4058
Some more small improvements. For me, this is a positive_review.
Last 10 new commits:
d5c8834  trac #16538: improve documentation of 'always_include_output'

275b653  included 'always_include_output' in _process_default_options_

4aee36f  description of always_include_output changed in Automaton.process

7c96f5c  Merge branch 'fsm/processiteratornondet' of https://www.math.aau.at/git/sage into fsm/processiteratornondet

1e31c86  Multitape automaton example

7861454  corrected typo and spacing in docstrings

dfa5a1a  trac #16538: reworded docstrings; fixed spacing

b22134f  trac #16538: introduce epsilon transition in multitape transducer examples

75e23d0  trac #16538: include documentation of __call__ via automethod and include into TOC

bcfbd24  Small improvements of documentation

comment:15 Changed 8 years ago by
 Branch changed from u/skropf/fsm/processiteratornondet to u/dkrenn/fsm/processiteratornondet
comment:16 Changed 8 years ago by
 Commit changed from bcfbd2408c706f7f4062d765e9cbc8cef0aa4058 to 878505996d89522748e8ca340c2cf9c15e382881
Branch pushed to git repo; I updated commit sha1. New commits:
8785059  small changes in doc

comment:17 Changed 8 years ago by
 Commit changed from 878505996d89522748e8ca340c2cf9c15e382881 to b75665ef08fbe657b5891f751eb7cce64ff81fd6
Branch pushed to git repo; I updated commit sha1. New commits:
b75665e  added ~ in a couple of hyperlinks to avoid showing self

comment:18 Changed 8 years ago by
A couple of minor changes after reviewing comments.
comment:19 Changed 8 years ago by
 Status changed from needs_review to positive_review
ok, reviewed all those changes. Merges cleanly with 6.3.rc0 (despite trac's automerge failure), doctests pass, documentation fine.
comment:20 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:21 Changed 8 years ago by
 Branch changed from u/dkrenn/fsm/processiteratornondet to b75665ef08fbe657b5891f751eb7cce64ff81fd6
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
FiniteStateMachine: rewritten code after #16067
FiniteStateMachine.deepcopy: additional doctest
Merge remotetracking branch 'aau/fsm/deepcopy_doctest' into fsm/codecleanuppost16067
trac #16580: use OrderedDict instead of dict to have nonrandom output
trac #16580: only use integer labels in doctests for latex_options
Merge commit '1bfb513ca3a9dc11a232bdd6ee31625fe5822572' (#16557) of trac.sagemath.org:sage into fsm/codecleanuppost16067
Merge remotetracking branch 'aau/fsm/codecleanuppost16067' into fsm/processiteratornondet
again some small corrections in doctests (word_in transposition)
trac #16538: word of tuples (instead of word of lists), one more transposition
reworded docstring