Vcsn
2.1
Be Rational
|
#include <synchronizing-word.hh>
Public Types | |
using | automaton_t = Aut |
using | word_t = word_t_of< automaton_t > |
using | state_t = state_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 | pair_t = std::pair< state_t, state_t > |
using | dist_transition_t = std::pair< unsigned, transition_t > |
using | paths_t = std::unordered_map< state_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_ |
pair_automaton< Aut > | pair_ |
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 100 of file synchronizing-word.hh.
|
private |
Definition at line 228 of file synchronizing-word.hh.
using vcsn::detail::word_synchronizer< Aut >::label_t = label_t_of<automaton_t> |
Definition at line 96 of file synchronizing-word.hh.
|
private |
Definition at line 99 of file synchronizing-word.hh.
|
private |
Definition at line 102 of file synchronizing-word.hh.
|
private |
Definition at line 101 of file synchronizing-word.hh.
using vcsn::detail::word_synchronizer< Aut >::state_t = state_t_of<automaton_t> |
Definition at line 94 of file synchronizing-word.hh.
using vcsn::detail::word_synchronizer< Aut >::transition_t = transition_t_of<automaton_t> |
Definition at line 95 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 111 of file synchronizing-word.hh.
|
inlineprivate |
Definition at line 168 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 183 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 207 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::cycle_().
Referenced by vcsn::synchronizing_word().
|
inlineprivate |
Definition at line 252 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::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 336 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 159 of file synchronizing-word.hh.
References 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 154 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 222 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::fastsynchro_().
Referenced by vcsn::synchronizing_word().
|
inlineprivate |
Definition at line 285 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::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 202 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 116 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 129 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 196 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 347 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::delta(), and vcsn::detail::word_synchronizer< Aut >::recompose_path().
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 359 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 366 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 >::fastsynchro_().
|
inlineprivate |
|
inlineprivate |
Definition at line 230 of file synchronizing-word.hh.
References vcsn::detail::word_synchronizer< Aut >::apply_path(), vcsn::detail::word_synchronizer< Aut >::init_synchro(), 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 212 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 217 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 |
Definition at line 104 of file synchronizing-word.hh.
|
private |
Definition at line 105 of file synchronizing-word.hh.
|
private |
Definition at line 106 of file synchronizing-word.hh.
|
private |
Definition at line 108 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 107 of file synchronizing-word.hh.