automaton::simplify::Minimize Class Reference

#include <Minimize.h>

Static Public Member Functions
template<class SymbolType , class StateType >
static automaton::DFA< SymbolType, StateType >	minimize (const automaton::DFA< SymbolType, StateType > &dfa)
template<class SymbolType , class StateType >
static automaton::DFA< SymbolType, StateType >	minimize (const automaton::DFA< SymbolType, StateType > &dfa, size_t &steps)
template<class SymbolType , class StateType >
static automaton::DFTA< SymbolType, StateType >	minimize (const automaton::DFTA< SymbolType, StateType > &dfta)
template<class SymbolType , class StateType >
static automaton::DFTA< SymbolType, StateType >	minimize (const automaton::DFTA< SymbolType, StateType > &dfta, size_t &steps)

Detailed Description

Minimization of automata.

For finite automata, we implement Hopcroft's subset minimization. For finite tree automata, we implement ???.

See also

automaton::simplify::MinimizeBrzozowski

automaton::simplify::MinimizeDistinguishableStates

Member Function Documentation

minimize() [1/4]

template<class SymbolType , class StateType >

static automaton::DFA< SymbolType, StateType > automaton::simplify::Minimize::minimize ( const automaton::DFA< SymbolType, StateType > &  dfa )

inlinestatic

Minimizes deterministic finite autmaton.

Template Parameters

SymbolType	Type for input symbols.
StateType	Type for states.

Parameters

dfa	deterministic finite automaton to minimize.

Returns

Minimal deterministic finite automaton equivalent to dfa

Here is the call graph for this function:

Here is the caller graph for this function:

minimize() [2/4]

template<class SymbolType , class StateType >

automaton::DFA< SymbolType, StateType > automaton::simplify::Minimize::minimize ( const automaton::DFA< SymbolType, StateType > &  dfa, size_t &  steps  )

static

Minimizes deterministic finite autmaton, also reports number of iterations it took.

Template Parameters

SymbolType	Type for input symbols.
StateType	Type for states.

Parameters

	dfa	deterministic finite automaton to minimize.
[out]	steps	Number of steps in the subset minimization performed until finished

Returns

Minimal deterministic finite automaton equivalent to dfa

Here is the call graph for this function:

minimize() [3/4]

template<class SymbolType , class StateType >

static automaton::DFTA< SymbolType, StateType > automaton::simplify::Minimize::minimize ( const automaton::DFTA< SymbolType, StateType > &  dfta )

inlinestatic

Minimizes deterministic finite tree autmaton.

Template Parameters

SymbolType	Type for input symbols.
RankType	Type for rank (arity) in ranked alphabet.
StateType	Type for states.

Parameters

dfta	deterministic finite tree automaton to minimize.

Returns

Minimal deterministic finite automaton equivalent to dfa

Here is the call graph for this function:

minimize() [4/4]

template<class SymbolType , class StateType >

automaton::DFTA< SymbolType, StateType > automaton::simplify::Minimize::minimize ( const automaton::DFTA< SymbolType, StateType > &  dfta, size_t &  steps  )

static

Minimizes deterministic finite tree autmaton, also reports number of iterations it took.

Template Parameters

SymbolType	Type for input symbols.
RankType	Type for rank (arity) in ranked alphabet.
StateType	Type for states.

Parameters

	dfta	deterministic finite tree automaton to minimize.
[out]	steps	Number of steps in the subset minimization performed until finished

Returns

Minimal deterministic finite automaton equivalent to dfa

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• alib2algo/src/automaton/simplify/Minimize.h