automaton::properties::DistinguishableStates Class Reference

#include <DistinguishableStates.h>

Static Public Member Functions
template<class SymbolType , class StateType >
static ext::set< ext::pair< StateType, StateType > >	distinguishable (const automaton::DFA< SymbolType, StateType > &fsm)
template<class SymbolType , class StateType >
static ext::set< ext::pair< StateType, StateType > >	distinguishable (const automaton::DFTA< SymbolType, StateType > &fta)
template<class SymbolType , class StateType >
static ext::set< ext::pair< StateType, StateType > >	distinguishable (const automaton::UnorderedDFTA< SymbolType, StateType > &fta)

Detailed Description

Find all distinguishable pairs of states of DFA. Implements table-filling algorithm, Hopcroft 2nd edition, 4.4.1

Member Function Documentation

distinguishable() [1/3]

template<class SymbolType , class StateType >

ext::set< ext::pair< StateType, StateType > > automaton::properties::DistinguishableStates::distinguishable ( const automaton::DFA< SymbolType, StateType > &  fsm )

static

Find all distinguishable pairs of states of DFA. Implements table-filling algorithm, Hopcroft 2nd edition, 4.4.1 O(n^4) version. TODO quadratic-time version.

Parameters

fsm

automaton

Returns

set of pairs of distinguishable states of fsm

Here is the call graph for this function:

Here is the caller graph for this function:

distinguishable() [2/3]

template<class SymbolType , class StateType >

ext::set< ext::pair< StateType, StateType > > automaton::properties::DistinguishableStates::distinguishable ( const automaton::DFTA< SymbolType, StateType > &  fta )

static

Here is the call graph for this function:

distinguishable() [3/3]

template<class SymbolType , class StateType >

ext::set< ext::pair< StateType, StateType > > automaton::properties::DistinguishableStates::distinguishable ( const automaton::UnorderedDFTA< SymbolType, StateType > &  fta )

static

Here is the call graph for this function:

---

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

• alib2algo/src/automaton/properties/DistinguishableStates.h