package grenier

  1. Overview
  2. Docs
A collection of various algorithms in OCaml

Install 

dune-project
 Dependency

github.com Readme Changelog Edit opam file Versions (12)

Authors

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Maintainers

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Sources

grenier-0.16.tbz
sha256=8fd22abf9f4589c206008654fa9eebb1cf4a58737ebb34138c6709520f36b75f
sha512=f60315eccfecaec9cb4c3bd020ef6f94d05ed6b13038109b904ead6e4e5662f4ed95415855b3c763293b762b696f1962045393fd592742d54cf5607d0ef2961a

doc/grenier.valmari/Valmari/Minimize/argument-2-In/index.html

Parameter Minimize.In

include DFA with type label := Label.t
type states

The set of DFA nodes

type transitions
val transitions : transitions Strong.Finite.set

The set of DFA transitions

Get the label associated with a transition

Get the source state of the transition

Get the target state of the transition

val initials : (states Strong.Finite.elt -> unit) -> unit

Iterate on initial states

val finals : (states Strong.Finite.elt -> unit) -> unit

Iterate final states

val refinements : refine:(iter:((states Strong.Finite.elt -> unit) -> unit) -> unit) -> unit

The minimization algorithms operate on a DFA plus an optional initial refinement (state that must be distinguished, because of some external properties not observable from the labelled transitions alone).

If no refinements are needed, the minimum implementation is just: let refinements ~refine:_ = ()

Otherwise, the refinements function should invoke the refine function for each set of equivalent states and call the iter for each equivalent state.

E.g if our automata has 5 states, and states 2 and 3 have tag A while states 4 and 5 have tag B, we will do:

let refinements ~refine = refine (fun ~iter -> iter 2; 3); refine (fun ~iter -> iter 4; 5)