Opened 8 years ago
Closed 8 years ago
#15925 closed defect (fixed)
Use Brzozowski' algorithm as default for minimizing non-deterministic automata
Reported by: | skropf | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.2 |
Component: | combinatorics | Keywords: | finite_state_machine |
Cc: | dkrenn, cheuberg | Merged in: | |
Authors: | Clemens Heuberger, Daniel Krenn, Sara Kropf | Reviewers: | Daniel Krenn |
Report Upstream: | N/A | Work issues: | |
Branch: | 3b545ad (Commits, GitHub, GitLab) | Commit: | 3b545ad2ab9cec17f4dfe09deeb265e8e00088e3 |
Dependencies: | Stopgaps: |
Description
For a non-deterministic automaton, just merging states which are indistinguishable for any suffix does not give a minimal non-deterministic automaton in every case (see e.g. http://cs.stackexchange.com/a/12712 ). This would be done by Moore's algorithm and only gives a smaller automaton. To obtain an equivalent minimal deterministic automaton, we use Brzozowski's algorithm, which first computes a determinisation of the non-deterministic automaton.
Change History (3)
comment:1 Changed 8 years ago by
- Branch set to u/cheuberg/fsm/brzozowski-default-for-nondeterministic-automata
- Commit set to 3b545ad2ab9cec17f4dfe09deeb265e8e00088e3
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Reviewers set to Daniel Krenn
- Status changed from needs_review to positive_review
I've rewritten parts of a docstring. Cross-checked by cheuberg. Everything looks fine, Doctests pass.code looks fine, docu checked, coverage checked.
comment:3 Changed 8 years ago by
- Branch changed from u/cheuberg/fsm/brzozowski-default-for-nondeterministic-automata to 3b545ad2ab9cec17f4dfe09deeb265e8e00088e3
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
Use Brzozowski as default for minimizing non-deterministic automata
Correct whitespace error
docstring (INPUT) of minimization rewritten
inserted "the" in docstring of minimization