#include <synchronizing-word.hh>

Collaboration diagram for vcsn::detail::word_synchronizer< Aut >:

Public Types
using	automaton_t = Aut

using	word_t = word_t_of< automaton_t >

using	transition_t = transition_t_of< automaton_t >

using	label_t = label_t_of< automaton_t >

Public Member Functions
	word_synchronizer (const automaton_t &aut)

bool	is_synchronizing ()

word_t	greedy ()

word_t	cycle ()

word_t	synchroP ()

word_t	synchroPL ()

word_t	fastsynchro ()

Private Types
using	state_t = state_t_of< automaton_t >

using	pair_automaton_t = pair_automaton< automaton_t >

using	state_name_t = std::pair< state_t, state_t >

using	dist_transition_t = std::pair< unsigned, transition_t_of< pair_automaton_t > >

using	paths_t = std::unordered_map< state_t_of< pair_automaton_t >, dist_transition_t >

using	path_t = typename paths_t::value_type

using	heuristic_t = auto(word_synchronizer::*)(state_t) const -> int

Private Member Functions
void	init_pair (bool keep_initials=false)

void	init_synchro (bool keep_initials=false)

std::vector< transition_t >	recompose_path (state_t from) const

int	dist (state_t s) const

state_t	dest_state (state_t s, const label_t &l) const

void	apply_label (const label_t &label)

void	apply_path (const std::vector< transition_t > &path)
	"Apply" a word to the set of active states (for each state, for each label, perform s = d(s)) More...

word_t	synchro (heuristic_t heuristic)

word_t	cycle_ ()

word_t	fastsynchro_ ()

int	delta (state_t p, const std::vector< transition_t > &w) const
	Compute dist(d(s, w)) - dist(s). More...

int	phi_1 (state_t p) const
	Heuristic used for SynchroP. More...

int	phi_2 (state_t p) const
	Heuristic used for SynchroPL. More...

int	phi_3 (const label_t &l) const
	Heuristic used for FastSynchro. More...

Private Attributes
automaton_t	aut_
	Input automaton. More...

pair_automaton_t	pair_
	Corresponding pair automaton. More...

paths_t	paths_

std::unordered_set< state_t >	todo_

word_t	res_

Detailed Description

template<Automaton Aut>
class vcsn::detail::word_synchronizer< Aut >

Definition at line 89 of file synchronizing-word.hh.

Member Typedef Documentation

◆ automaton_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::automaton_t = Aut

Definition at line 92 of file synchronizing-word.hh.

◆ dist_transition_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::dist_transition_t = std::pair<unsigned, transition_t_of<pair_automaton_t> >

private

Definition at line 104 of file synchronizing-word.hh.

◆ heuristic_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::heuristic_t = auto (word_synchronizer::*)(state_t) const -> int

private

Definition at line 235 of file synchronizing-word.hh.

◆ label_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::label_t = label_t_of<automaton_t>

Definition at line 95 of file synchronizing-word.hh.

◆ pair_automaton_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::pair_automaton_t = pair_automaton<automaton_t>

private

Definition at line 100 of file synchronizing-word.hh.

◆ path_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::path_t = typename paths_t::value_type

private

Definition at line 107 of file synchronizing-word.hh.

◆ paths_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::paths_t = std::unordered_map<state_t_of<pair_automaton_t>, dist_transition_t>

private

Definition at line 106 of file synchronizing-word.hh.

◆ state_name_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::state_name_t = std::pair<state_t, state_t>

private

Definition at line 101 of file synchronizing-word.hh.

◆ state_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::state_t = state_t_of<automaton_t>

private

Definition at line 98 of file synchronizing-word.hh.

◆ transition_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::transition_t = transition_t_of<automaton_t>

Definition at line 94 of file synchronizing-word.hh.

◆ word_t

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::word_t = word_t_of<automaton_t>

Definition at line 93 of file synchronizing-word.hh.

Constructor & Destructor Documentation

◆ word_synchronizer()

template<Automaton Aut>

vcsn::detail::word_synchronizer< Aut >::word_synchronizer ( const automaton_t & aut )

inline

Definition at line 118 of file synchronizing-word.hh.

Member Function Documentation

◆ apply_label()

template<Automaton Aut>

void vcsn::detail::word_synchronizer< Aut >::apply_label ( const label_t & label )

inlineprivate

Definition at line 175 of file synchronizing-word.hh.

◆ apply_path()

template<Automaton Aut>

void vcsn::detail::word_synchronizer< Aut >::apply_path ( const std::vector< transition_t > & path )

inlineprivate

"Apply" a word to the set of active states (for each state, for each label, perform s = d(s))

Definition at line 190 of file synchronizing-word.hh.

◆ cycle()

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::cycle ( )

inline

Definition at line 214 of file synchronizing-word.hh.

Referenced by vcsn::synchronizing_word().

◆ cycle_()

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::cycle_ ( )

inlineprivate

Definition at line 259 of file synchronizing-word.hh.

References vcsn::min.

◆ delta()

template<Automaton Aut>

int vcsn::detail::word_synchronizer< Aut >::delta	(	state_t	p,
		const std::vector< transition_t > &	w
	)		const

inlineprivate

Compute dist(d(s, w)) - dist(s).

Definition at line 343 of file synchronizing-word.hh.

◆ dest_state()

template<Automaton Aut>

state_t vcsn::detail::word_synchronizer< Aut >::dest_state	(	state_t	s,
		const label_t &	l
	)		const

inlineprivate

Definition at line 166 of file synchronizing-word.hh.

References vcsn::detail::out(), vcsn::require(), and vcsn::rat::size().

Here is the call graph for this function:

◆ dist()

template<Automaton Aut>

int vcsn::detail::word_synchronizer< Aut >::dist ( state_t s ) const

inlineprivate

Definition at line 161 of file synchronizing-word.hh.

◆ fastsynchro()

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::fastsynchro ( )

inline

Definition at line 229 of file synchronizing-word.hh.

Referenced by vcsn::synchronizing_word().

◆ fastsynchro_()

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::fastsynchro_ ( )

inlineprivate

Definition at line 292 of file synchronizing-word.hh.

References vcsn::min.

◆ greedy()

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::greedy ( )

inline

Definition at line 209 of file synchronizing-word.hh.

Referenced by vcsn::synchronizing_word().

◆ init_pair()

template<Automaton Aut>

void vcsn::detail::word_synchronizer< Aut >::init_pair ( bool keep_initials = false )

inlineprivate

Definition at line 123 of file synchronizing-word.hh.

References vcsn::detail::erase_if(), vcsn::dyn::detail::pair(), and vcsn::paths_ibfs().

Here is the call graph for this function:

◆ init_synchro()

template<Automaton Aut>

void vcsn::detail::word_synchronizer< Aut >::init_synchro ( bool keep_initials = false )

inlineprivate

Definition at line 136 of file synchronizing-word.hh.

References vcsn::require().

Here is the call graph for this function:

◆ is_synchronizing()

template<Automaton Aut>

bool vcsn::detail::word_synchronizer< Aut >::is_synchronizing ( )

inline

Definition at line 203 of file synchronizing-word.hh.

Referenced by vcsn::is_synchronizing().

◆ phi_1()

template<Automaton Aut>

int vcsn::detail::word_synchronizer< Aut >::phi_1 ( state_t p ) const

inlineprivate

Heuristic used for SynchroP.

phi_1(p) = Sum delta(s, w) for all s in the active states, with s != p. w is the shortest word that syncs the pair p.

Definition at line 354 of file synchronizing-word.hh.

References vcsn::res.

◆ phi_2()

template<Automaton Aut>

int vcsn::detail::word_synchronizer< Aut >::phi_2 ( state_t p ) const

inlineprivate

Heuristic used for SynchroPL.

phi2(p) = phi_1(p).

Definition at line 366 of file synchronizing-word.hh.

◆ phi_3()

template<Automaton Aut>

int vcsn::detail::word_synchronizer< Aut >::phi_3 ( const label_t & l ) const

inlineprivate

Heuristic used for FastSynchro.

phi3(l) = Sum dist(d(s, l)) - dist(s) forall s in the active states.

Definition at line 373 of file synchronizing-word.hh.

References vcsn::res.

◆ recompose_path()

template<Automaton Aut>

std::vector<transition_t> vcsn::detail::word_synchronizer< Aut >::recompose_path ( state_t from ) const

inlineprivate

Definition at line 148 of file synchronizing-word.hh.

References vcsn::res.

◆ synchro()

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::synchro ( heuristic_t heuristic )

inlineprivate

Definition at line 237 of file synchronizing-word.hh.

References vcsn::min.

◆ synchroP()

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::synchroP ( )

inline

Definition at line 219 of file synchronizing-word.hh.

Referenced by vcsn::synchronizing_word().

◆ synchroPL()

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::synchroPL ( )

inline

Definition at line 224 of file synchronizing-word.hh.

Referenced by vcsn::synchronizing_word().

Member Data Documentation

◆ aut_

template<Automaton Aut>

automaton_t vcsn::detail::word_synchronizer< Aut >::aut_

private

Input automaton.

Definition at line 110 of file synchronizing-word.hh.

◆ pair_

template<Automaton Aut>

pair_automaton_t vcsn::detail::word_synchronizer< Aut >::pair_

private

Corresponding pair automaton.

Definition at line 112 of file synchronizing-word.hh.

◆ paths_

template<Automaton Aut>

paths_t vcsn::detail::word_synchronizer< Aut >::paths_

private

Definition at line 113 of file synchronizing-word.hh.

◆ res_

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::res_

private

Definition at line 115 of file synchronizing-word.hh.

◆ todo_

template<Automaton Aut>

std::unordered_set<state_t> vcsn::detail::word_synchronizer< Aut >::todo_

private

Definition at line 114 of file synchronizing-word.hh.

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

vcsn/algos/synchronizing-word.hh

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<Automaton Aut> class vcsn::detail::word_synchronizer< Aut >

Member Typedef Documentation

◆ automaton_t

◆ dist_transition_t

◆ heuristic_t

◆ label_t

◆ pair_automaton_t

◆ path_t

◆ paths_t

◆ state_name_t

◆ state_t

◆ transition_t

◆ word_t

Constructor & Destructor Documentation

◆ word_synchronizer()

Member Function Documentation

◆ apply_label()

◆ apply_path()

◆ cycle()

◆ cycle_()

◆ delta()

◆ dest_state()

◆ dist()

◆ fastsynchro()

◆ fastsynchro_()

◆ greedy()

◆ init_pair()

◆ init_synchro()

◆ is_synchronizing()

◆ phi_1()

◆ phi_2()

◆ phi_3()

◆ recompose_path()

◆ synchro()

◆ synchroP()

◆ synchroPL()

Member Data Documentation

◆ aut_

◆ pair_

◆ paths_

◆ res_

◆ todo_

template<Automaton Aut>
class vcsn::detail::word_synchronizer< Aut >