#15848: Simplification for non-deterministic transducers via Moore's algorithm
-------------------------------------+-------------------------------------
Reporter: cheuberg | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.2
Component: combinatorics | Resolution:
Keywords: | Merged in:
finite_state_machine | Reviewers:
Authors: Clemens | Work issues:
Heuberger, Daniel Krenn | Commit:
Report Upstream: N/A | 336de301a7510e2005c7302d6aa1ebd796be66d1
Branch: u/cheuberg/fsm | Stopgaps:
/moore-non-deterministic |
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Clemens Heuberger, Daniel Krenn', 'oldvalue':
u'Clemens Heuberger'}):
* status: new => needs_review
* author: Clemens Heuberger => Clemens Heuberger, Daniel Krenn
* cc: dkrenn (added)
* branch: => u/cheuberg/fsm/moore-non-deterministic
* commit: => 336de301a7510e2005c7302d6aa1ebd796be66d1
Old description:
> In the current implementation, Non-deterministic transducers cannot be
> simplified via Moore's algorithm.
>
> I am preparing a patch and will push it in a few days.
New description:
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.
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=e5860f54ecf3390e5e8daf127b1c97d57580097f
e5860f5]||{{{Inserted DocTest: No Simplification for non-deterministic
Transducers.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=1c123b47a3331d8dfbc65a329f37438d1db3e172
1c123b4]||{{{Simplification for non-deterministic transducers via Moore's
algorithm}}}||
||[http://git.sagemath.org/sage.git/commit/?id=4e6864530acb5cd1ca64c504443d23b0d3a0d5ad
4e68645]||{{{description of equivalent states rewritten}}}||
||[http://git.sagemath.org/sage.git/commit/?id=f065517acba6ec3cf6e9f0ad231fdc7d2fb494af
f065517]||{{{docstring in quotient adapted to the same style as
equivalence classes}}}||
||[http://git.sagemath.org/sage.git/commit/?id=336de301a7510e2005c7302d6aa1ebd796be66d1
336de30]||{{{small changes in docstring of _minimization_Moore_}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/15848#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
