FiniteStateMachine.process: follow all paths if machine is non-deterministic

cheuberg commented 10 years ago

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 non-deterministic machines, all possible paths should be considered. This shall be implemented in this ticket.

CC: @dkrenn @sagetrac-skropf

Component: finite state machines

Author: Daniel Krenn

Branch/Commit: b75665e

Reviewer: Clemens Heuberger, Sara Kropf

Issue created by migration from https://trac.sagemath.org/ticket/16538

cheuberg commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,4 @@
-Currently, a (more or less) random path was chosen in case of ambiguity
-in `FiniteStateMachine.process`. In the case of non-deterministic machines,
-all possible paths should be considered.
+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 non-deterministic machines, all possible paths should be considered. This shall be implemented in this ticket. Daniel Krenn is in the process of preparing a branch.

dkrenn commented 10 years ago

Branch: u/dkrenn/fsm/process-iterator-nondet

dkrenn commented 10 years ago

Last 10 new commits:

`07e353a`	`FiniteStateMachine: rewritten code after #16067`
`f9d6e0e`	`FiniteStateMachine.deepcopy: additional doctest`
`fd618dc`	`Merge remote-tracking branch 'aau/fsm/deepcopy_doctest' into fsm/code-cleanup-post-16067`
`4eef9c8`	`trac #16580: use OrderedDict instead of dict to have non-random output`
`6dc0eca`	`trac #16580: only use integer labels in doctests for latex_options`
`102be36`	`Merge commit '1bfb513ca3a9dc11a232bdd6ee31625fe5822572' (#16557) of trac.sagemath.org:sage into fsm/code-cleanup-post-16067`
`7e225f1`	`Merge remote-tracking branch 'aau/fsm/code-cleanup-post-16067' into fsm/process-iterator-nondet`
`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`

dkrenn commented 10 years ago

Commit: 51d35dc

dkrenn commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
 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 non-deterministic machines, all possible paths should be considered. This shall be implemented in this ticket. Daniel Krenn is in the process of preparing a branch.
+However, ideally, in the case of non-deterministic machines, all possible paths should be considered. This shall be implemented in this ticket.

dkrenn commented 10 years ago

Author: Daniel Krenn

cheuberg commented 10 years ago

comment:4

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.

cheuberg commented 10 years ago

Reviewer: Clemens Heuberger

cheuberg commented 10 years ago

Changed branch from u/dkrenn/fsm/process-iterator-nondet to u/cheuberg/fsm/process-iterator-nondet

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`1417c7d`	`trac #16538: correct overlooked renamed variable`
`4bbf3a5`	`trac #16538: correct second overlooked renamed variable`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 51d35dc to 4bbf3a5

dkrenn commented 10 years ago

Changed branch from u/cheuberg/fsm/process-iterator-nondet to u/dkrenn/fsm/process-iterator-nondet

cheuberg commented 10 years ago

comment:8

Clear "commit" field so that Daniel's new branch is actually used.

Last 10 new commits:

`7e225f1`	`Merge remote-tracking branch 'aau/fsm/code-cleanup-post-16067' into fsm/process-iterator-nondet`
`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`

cheuberg commented 10 years ago

Changed commit from 4bbf3a5 to 4aee36f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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/process-iterator-nondet' of https://www.math.aau.at/git/sage into fsm/process-iterator-nondet`
`0218129`	`Finite State Machine: rearrangement of parameters explanation in process`
`1c442bc`	`Multi-tape FSM and transducer example in process`
`7c96f5c`	`Merge branch 'fsm/process-iterator-nondet' of https://www.math.aau.at/git/sage into fsm/process-iterator-nondet`
`1e31c86`	`Multi-tape automaton example`
`7861454`	`corrected typo and spacing in docstrings`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 4aee36f to 7861454

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

comment:10

I improved parts of the documentation. Especially, those of the high level functions.

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

Changed reviewer from Clemens Heuberger to Clemens Heuberger, Sara Kropf

cheuberg commented 10 years ago

Changed branch from u/dkrenn/fsm/process-iterator-nondet to u/cheuberg/fsm/process-iterator-nondet

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 7861454 to 75e23d0

cheuberg commented 10 years ago

comment:13

Replying to @sagetrac-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 sage-devel, the docstring of __call__ is now included into the reference manual.

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

Changed commit from 75e23d0 to bcfbd24

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

Changed branch from u/cheuberg/fsm/process-iterator-nondet to u/skropf/fsm/process-iterator-nondet

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

comment:14

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/process-iterator-nondet' of https://www.math.aau.at/git/sage into fsm/process-iterator-nondet`
`1e31c86`	`Multi-tape 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`

dkrenn commented 10 years ago

Changed branch from u/skropf/fsm/process-iterator-nondet to u/dkrenn/fsm/process-iterator-nondet

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

8785059 small changes in doc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from bcfbd24 to 8785059

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

b75665e added ~ in a couple of hyperlinks to avoid showing self

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 8785059 to b75665e

dkrenn commented 10 years ago

comment:18

A couple of minor changes after reviewing comments.

cheuberg commented 10 years ago

comment:19

ok, reviewed all those changes. Merges cleanly with 6.3.rc0 (despite trac's automerge failure), doctests pass, documentation fine.

vbraun commented 10 years ago

Changed branch from u/dkrenn/fsm/process-iterator-nondet to b75665e

sagemath / sage

FiniteStateMachine.process: follow all paths if machine is non-deterministic #16538