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:

Status badges

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 cheuberg

  • Branch set to u/cheuberg/fsm/brzozowski-default-for-nondeterministic-automata
  • Commit set to 3b545ad2ab9cec17f4dfe09deeb265e8e00088e3
  • Status changed from new to needs_review

New commits:

e0c7782Use Brzozowski as default for minimizing non-deterministic automata
7b0d6faCorrect whitespace error
9611104docstring (INPUT) of minimization rewritten
3b545adinserted "the" in docstring of minimization

comment:2 Changed 8 years ago by dkrenn

  • 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.

Last edited 8 years ago by dkrenn (previous) (diff)

comment:3 Changed 8 years ago by vbraun

  • Branch changed from u/cheuberg/fsm/brzozowski-default-for-nondeterministic-automata to 3b545ad2ab9cec17f4dfe09deeb265e8e00088e3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.