![]() |
Vcsn
2.3a
Be Rational
|
#include <synchronizing-word.hh>
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_ |
Definition at line 89 of file synchronizing-word.hh.
using vcsn::detail::word_synchronizer< Aut >::automaton_t = Aut |
Definition at line 92 of file synchronizing-word.hh.
|
private |
Definition at line 104 of file synchronizing-word.hh.
|
private |
Definition at line 235 of file synchronizing-word.hh.
using vcsn::detail::word_synchronizer< Aut >::label_t = label_t_of<automaton_t> |
Definition at line 95 of file synchronizing-word.hh.
|
private |
Definition at line 100 of file synchronizing-word.hh.
|
private |
Definition at line 107 of file synchronizing-word.hh.
|
private |
Definition at line 106 of file synchronizing-word.hh.
|
private |
Definition at line 101 of file synchronizing-word.hh.
|
private |
Definition at line 98 of file synchronizing-word.hh.
using vcsn::detail::word_synchronizer< Aut >::transition_t = transition_t_of<automaton_t> |
Definition at line 94 of file synchronizing-word.hh.
using vcsn::detail::word_synchronizer< Aut >::word_t = word_t_of<automaton_t> |
Definition at line 93 of file synchronizing-word.hh.
|
inline |
Definition at line 118 of file synchronizing-word.hh.
|
inlineprivate |
Definition at line 175 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::dest_state().
Referenced by vcsn::detail::word_synchronizer< Aut >::apply_path(), and vcsn::detail::word_synchronizer< Aut >::fastsynchro_().
|
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.
References vcsn::detail::word_synchronizer< Aut >::apply_label().
Referenced by vcsn::detail::word_synchronizer< Aut >::cycle_(), vcsn::detail::word_synchronizer< Aut >::fastsynchro_(), and vcsn::detail::word_synchronizer< Aut >::synchro().
|
inline |
Definition at line 214 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::cycle_().
Referenced by vcsn::synchronizing_word().
|
inlineprivate |
Definition at line 259 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::apply_path(), vcsn::detail::word_synchronizer< Aut >::dist(), vcsn::detail::word_synchronizer< Aut >::init_synchro(), vcsn::min, vcsn::detail::word_synchronizer< Aut >::recompose_path(), and vcsn::detail::word_synchronizer< Aut >::res_.
Referenced by vcsn::detail::word_synchronizer< Aut >::cycle().
|
inlineprivate |
Compute dist(d(s, w)) - dist(s).
Definition at line 343 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::dest_state(), and vcsn::detail::word_synchronizer< Aut >::dist().
Referenced by vcsn::detail::word_synchronizer< Aut >::phi_1().
|
inlineprivate |
Definition at line 166 of file synchronizing-word.hh.
References vcsn::detail::out(), vcsn::require(), and vcsn::rat::size().
Referenced by vcsn::detail::word_synchronizer< Aut >::apply_label(), vcsn::detail::word_synchronizer< Aut >::delta(), and vcsn::detail::word_synchronizer< Aut >::phi_3().
|
inlineprivate |
Definition at line 161 of file synchronizing-word.hh.
Referenced by vcsn::detail::word_synchronizer< Aut >::cycle_(), vcsn::detail::word_synchronizer< Aut >::delta(), vcsn::detail::word_synchronizer< Aut >::greedy(), vcsn::detail::word_synchronizer< Aut >::phi_2(), and vcsn::detail::word_synchronizer< Aut >::phi_3().
|
inline |
Definition at line 229 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::fastsynchro_().
Referenced by vcsn::synchronizing_word().
|
inlineprivate |
Definition at line 292 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::apply_label(), vcsn::detail::word_synchronizer< Aut >::apply_path(), vcsn::detail::word_synchronizer< Aut >::init_synchro(), vcsn::min, vcsn::detail::word_synchronizer< Aut >::phi_2(), vcsn::detail::word_synchronizer< Aut >::phi_3(), vcsn::detail::word_synchronizer< Aut >::recompose_path(), and vcsn::detail::word_synchronizer< Aut >::res_.
Referenced by vcsn::detail::word_synchronizer< Aut >::fastsynchro().
|
inline |
Definition at line 209 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::dist(), and vcsn::detail::word_synchronizer< Aut >::synchro().
Referenced by vcsn::synchronizing_word().
|
inlineprivate |
Definition at line 123 of file synchronizing-word.hh.
References vcsn::detail::erase_if(), vcsn::pair(), and vcsn::paths_ibfs().
Referenced by vcsn::detail::word_synchronizer< Aut >::init_synchro(), and vcsn::detail::word_synchronizer< Aut >::is_synchronizing().
|
inlineprivate |
Definition at line 136 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::init_pair(), and vcsn::require().
Referenced by vcsn::detail::word_synchronizer< Aut >::cycle_(), vcsn::detail::word_synchronizer< Aut >::fastsynchro_(), and vcsn::detail::word_synchronizer< Aut >::synchro().
|
inline |
Definition at line 203 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::init_pair().
Referenced by vcsn::is_synchronizing().
|
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::detail::word_synchronizer< Aut >::delta(), vcsn::detail::word_synchronizer< Aut >::recompose_path(), and vcsn::res.
Referenced by vcsn::detail::word_synchronizer< Aut >::phi_2(), and vcsn::detail::word_synchronizer< Aut >::synchroP().
|
inlineprivate |
Heuristic used for SynchroPL.
phi2(p) = phi_1(p).
Definition at line 366 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::dist(), and vcsn::detail::word_synchronizer< Aut >::phi_1().
Referenced by vcsn::detail::word_synchronizer< Aut >::fastsynchro_(), and vcsn::detail::word_synchronizer< Aut >::synchroPL().
|
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::detail::word_synchronizer< Aut >::dest_state(), vcsn::detail::word_synchronizer< Aut >::dist(), and vcsn::res.
Referenced by vcsn::detail::word_synchronizer< Aut >::fastsynchro_().
|
inlineprivate |
Definition at line 148 of file synchronizing-word.hh.
References vcsn::res.
Referenced by vcsn::detail::word_synchronizer< Aut >::cycle_(), vcsn::detail::word_synchronizer< Aut >::fastsynchro_(), vcsn::detail::word_synchronizer< Aut >::phi_1(), and vcsn::detail::word_synchronizer< Aut >::synchro().
|
inlineprivate |
Definition at line 237 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::apply_path(), vcsn::detail::word_synchronizer< Aut >::init_synchro(), vcsn::min, vcsn::detail::word_synchronizer< Aut >::recompose_path(), and vcsn::detail::word_synchronizer< Aut >::res_.
Referenced by vcsn::detail::word_synchronizer< Aut >::greedy(), vcsn::detail::word_synchronizer< Aut >::synchroP(), and vcsn::detail::word_synchronizer< Aut >::synchroPL().
|
inline |
Definition at line 219 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::phi_1(), and vcsn::detail::word_synchronizer< Aut >::synchro().
Referenced by vcsn::synchronizing_word().
|
inline |
Definition at line 224 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::phi_2(), and vcsn::detail::word_synchronizer< Aut >::synchro().
Referenced by vcsn::synchronizing_word().
|
private |
Input automaton.
Definition at line 110 of file synchronizing-word.hh.
|
private |
Corresponding pair automaton.
Definition at line 112 of file synchronizing-word.hh.
|
private |
Definition at line 113 of file synchronizing-word.hh.
|
private |
Definition at line 115 of file synchronizing-word.hh.
Referenced by vcsn::detail::word_synchronizer< Aut >::cycle_(), vcsn::detail::word_synchronizer< Aut >::fastsynchro_(), and vcsn::detail::word_synchronizer< Aut >::synchro().
|
private |
Definition at line 114 of file synchronizing-word.hh.