Opened 8 years ago

Closed 7 years ago

#16538 closed defect (fixed)

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

Reported by: cheuberg Owned by:
Priority: major Milestone: sage-6.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:

Status badges

Description (last modified by dkrenn)

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.

Change History (21)

comment:1 Changed 8 years ago by cheuberg

  • Description modified (diff)

comment:2 Changed 7 years ago by dkrenn

  • Branch set to u/dkrenn/fsm/process-iterator-nondet

comment:3 Changed 7 years ago by dkrenn

  • Authors set to Daniel Krenn
  • Commit set to 51d35dc08fc621267d95919eb07bb5017bb653bd
  • Description modified (diff)
  • Status changed from new to needs_review

Last 10 new commits:

07e353aFiniteStateMachine: rewritten code after #16067
f9d6e0eFiniteStateMachine.deepcopy: additional doctest
fd618dcMerge remote-tracking branch 'aau/fsm/deepcopy_doctest' into fsm/code-cleanup-post-16067
4eef9c8trac #16580: use OrderedDict instead of dict to have non-random output
6dc0ecatrac #16580: only use integer labels in doctests for latex_options
102be36Merge commit '1bfb513ca3a9dc11a232bdd6ee31625fe5822572' (#16557) of trac.sagemath.org:sage into fsm/code-cleanup-post-16067
7e225f1Merge remote-tracking branch 'aau/fsm/code-cleanup-post-16067' into fsm/process-iterator-nondet
59d736bagain some small corrections in doctests (word_in transposition)
15d09a9trac #16538: word of tuples (instead of word of lists), one more transposition
51d35dcreworded docstring

comment:4 Changed 7 years ago by cheuberg

  • 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 7 years ago by cheuberg

  • Branch changed from u/dkrenn/fsm/process-iterator-nondet to u/cheuberg/fsm/process-iterator-nondet

comment:6 Changed 7 years ago by git

  • Commit changed from 51d35dc08fc621267d95919eb07bb5017bb653bd to 4bbf3a54b51896447d601e046aff372f398498c6

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

1417c7dtrac #16538: correct overlooked renamed variable
4bbf3a5trac #16538: correct second overlooked renamed variable

comment:7 Changed 7 years ago by dkrenn

  • Branch changed from u/cheuberg/fsm/process-iterator-nondet to u/dkrenn/fsm/process-iterator-nondet

comment:8 Changed 7 years ago by cheuberg

  • Commit changed from 4bbf3a54b51896447d601e046aff372f398498c6 to 4aee36f7ecadc6b04a6ba62ac4c5961d76249133

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


Last 10 new commits:

7e225f1Merge remote-tracking branch 'aau/fsm/code-cleanup-post-16067' into fsm/process-iterator-nondet
59d736bagain some small corrections in doctests (word_in transposition)
15d09a9trac #16538: word of tuples (instead of word of lists), one more transposition
51d35dcreworded docstring
1417c7dtrac #16538: correct overlooked renamed variable
4bbf3a5trac #16538: correct second overlooked renamed variable
9250ad9trac #16538: add parameter 'always_include_output' for compatibility
d5c8834trac #16538: improve documentation of 'always_include_output'
275b653included 'always_include_output' in _process_default_options_
4aee36fdescription of always_include_output changed in Automaton.process

comment:9 Changed 7 years ago by git

  • Commit changed from 4aee36f7ecadc6b04a6ba62ac4c5961d76249133 to 7861454364d8d6aa62fbee79c7b03c84223e7f91

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

e4829c3FiniteStateMachine: Improvements of the documentation of __call__ and process
4bf7193Merge branch 'fsm/process-iterator-nondet' of https://www.math.aau.at/git/sage into fsm/process-iterator-nondet
0218129Finite State Machine: rearrangement of parameters explanation in process
1c442bcMulti-tape FSM and transducer example in process
7c96f5cMerge branch 'fsm/process-iterator-nondet' of https://www.math.aau.at/git/sage into fsm/process-iterator-nondet
1e31c86Multi-tape automaton example
7861454corrected typo and spacing in docstrings

comment:10 follow-up: Changed 7 years ago by skropf

  • 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 7 years ago by cheuberg

  • Branch changed from u/dkrenn/fsm/process-iterator-nondet to u/cheuberg/fsm/process-iterator-nondet

comment:12 Changed 7 years ago by git

  • Commit changed from 7861454364d8d6aa62fbee79c7b03c84223e7f91 to 75e23d083a840ada2308678fc67a0f0eeda59aa9

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

dfa5a1atrac #16538: reworded docstrings; fixed spacing
b22134ftrac #16538: introduce epsilon transition in multitape transducer examples
75e23d0trac #16538: include documentation of __call__ via automethod and include into TOC

comment:13 in reply to: ↑ 10 Changed 7 years ago by cheuberg

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

comment:14 Changed 7 years ago by skropf

  • Branch changed from u/cheuberg/fsm/process-iterator-nondet to u/skropf/fsm/process-iterator-nondet
  • Commit changed from 75e23d083a840ada2308678fc67a0f0eeda59aa9 to bcfbd2408c706f7f4062d765e9cbc8cef0aa4058

Some more small improvements. For me, this is a positive_review.


Last 10 new commits:

d5c8834trac #16538: improve documentation of 'always_include_output'
275b653included 'always_include_output' in _process_default_options_
4aee36fdescription of always_include_output changed in Automaton.process
7c96f5cMerge branch 'fsm/process-iterator-nondet' of https://www.math.aau.at/git/sage into fsm/process-iterator-nondet
1e31c86Multi-tape automaton example
7861454corrected typo and spacing in docstrings
dfa5a1atrac #16538: reworded docstrings; fixed spacing
b22134ftrac #16538: introduce epsilon transition in multitape transducer examples
75e23d0trac #16538: include documentation of __call__ via automethod and include into TOC
bcfbd24Small improvements of documentation

comment:15 Changed 7 years ago by dkrenn

  • Branch changed from u/skropf/fsm/process-iterator-nondet to u/dkrenn/fsm/process-iterator-nondet

comment:16 Changed 7 years ago by git

  • Commit changed from bcfbd2408c706f7f4062d765e9cbc8cef0aa4058 to 878505996d89522748e8ca340c2cf9c15e382881

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

8785059small changes in doc

comment:17 Changed 7 years ago by git

  • Commit changed from 878505996d89522748e8ca340c2cf9c15e382881 to b75665ef08fbe657b5891f751eb7cce64ff81fd6

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

b75665eadded ~ in a couple of hyperlinks to avoid showing self

comment:18 Changed 7 years ago by dkrenn

A couple of minor changes after reviewing comments.

comment:19 Changed 7 years ago by cheuberg

  • 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 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:21 Changed 7 years ago by vbraun

  • Branch changed from u/dkrenn/fsm/process-iterator-nondet to b75665ef08fbe657b5891f751eb7cce64ff81fd6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.