Opened 8 years ago

Closed 8 years ago

#15848 closed enhancement (fixed)

Simplification for non-deterministic transducers via Moore's algorithm

Reported by: cheuberg Owned by:
Priority: minor Milestone: sage-6.2
Component: combinatorics Keywords: finite_state_machine
Cc: Merged in:
Authors: Clemens Heuberger, Daniel Krenn Reviewers: Daniel Krenn
Report Upstream: N/A Work issues:
Branch: 336de30 (Commits, GitHub, GitLab) Commit: 336de301a7510e2005c7302d6aa1ebd796be66d1
Dependencies: Stopgaps:

Status badges

Description (last modified by cheuberg)

Previously, non-deterministic transducers could not be simplified via Moore's algorithm. In fact, the old code was already able to do that, but an error was thrown nevertheless. This check has been moved to minimization of Automata, because it is still required there.

Otherwise, the docstrings have been adapted to explain this generalization.

Finally, the old docstring of _minimization_Moore_ erroneously claimed to run Brzozowski's algorithm, which is now corrected.

Change History (5)

comment:1 Changed 8 years ago by cheuberg

  • Authors changed from Clemens Heuberger to Clemens Heuberger, Daniel Krenn
  • Branch set to u/cheuberg/fsm/moore-non-deterministic
  • Cc dkrenn added
  • Commit set to 336de301a7510e2005c7302d6aa1ebd796be66d1
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

​e5860f5Inserted DocTest: No Simplification for non-deterministic Transducers.
​1c123b4Simplification for non-deterministic transducers via Moore's algorithm
​4e68645description of equivalent states rewritten
​f065517docstring in quotient adapted to the same style as equivalence classes
​336de30small changes in docstring of _minimization_Moore_

comment:2 Changed 8 years ago by dkrenn

  • Cc dkrenn removed
  • Reviewers set to Daniel Krenn

comment:3 Changed 8 years ago by dkrenn

  • Status changed from needs_review to positive_review

comment:4 Changed 8 years ago by dkrenn

Docstrings rewritten. Cross-checked by cheuberg.

code looks fine, doctests pass, docu checked, coverage checked

comment:5 Changed 8 years ago by vbraun

  • Branch changed from u/cheuberg/fsm/moore-non-deterministic to 336de301a7510e2005c7302d6aa1ebd796be66d1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.