Vcsn  2.2
Be Rational
is-ambiguous.hh
Go to the documentation of this file.
1 #pragma once
2 
5 #include <vcsn/algos/conjunction.hh> // conjunction
6 #include <vcsn/algos/scc.hh>
7 #include <vcsn/dyn/fwd.hh>
8 #include <vcsn/dyn/label.hh>
9 
10 namespace vcsn
11 {
12 
13  /*---------------.
14  | is_ambiguous. |
15  `---------------*/
16 
22  template <Automaton Aut>
23  bool is_ambiguous(const Aut& aut,
25  {
26  auto prod = conjunction(aut, aut);
27  // Check if there useful states outside of the diagonal. Since
28  // the conjunction is accessible, check only for coaccessibles states.
29  auto coaccessible = coaccessible_states(prod);
30  for (const auto& o: prod->origins())
31  if (std::get<0>(o.second) != std::get<1>(o.second)
32  && has(coaccessible, o.first))
33  {
34  witness = o.second;
35  return true;
36  }
37  return false;
38  }
39 
40  template <Automaton Aut>
41  bool is_ambiguous(const Aut& aut)
42  {
43  std::tuple<state_t_of<Aut>, state_t_of<Aut>> dummy;
44  return is_ambiguous(aut, dummy);
45  }
46 
47  namespace dyn
48  {
49  namespace detail
50  {
52  template <Automaton Aut>
53  bool is_ambiguous(const automaton& aut)
54  {
55  return is_ambiguous(aut->as<Aut>());
56  }
57  }
58  }
59 
60 
61  /*-----------------.
62  | ambiguous_word. |
63  `-----------------*/
64 
65  template <Automaton Aut>
67  {
68  std::tuple<state_t_of<Aut>, state_t_of<Aut>> witness;
69  require(is_ambiguous(aut, witness),
70  "automaton is unambiguous");
71  const auto& ls = *aut->labelset();
72  // Find the shortest word from initial to the witness.
73  auto s = std::get<0>(witness);
74 
75  auto pre_to_s = path_monomial(aut, lightest_path(aut, aut->pre(), s),
76  aut->pre(), s);
77  auto s_to_post = path_monomial(aut, lightest_path(aut, s, aut->post()),
78  s, aut->post());
79  require(pre_to_s, "ambiguous_word: did not find monomial");
80  require(s_to_post, "ambiguous_word: did not find monomial");
81 
82  return ls.mul(pre_to_s->first, s_to_post->first);
83  }
84 
85 
86  namespace dyn
87  {
88  namespace detail
89  {
91  template <Automaton Aut>
92  label
94  {
95  const auto& a = aut->as<Aut>();
96  auto word = vcsn::ambiguous_word(a);
97  return make_label(make_wordset(*a->labelset()), word);
98  }
99  }
100  }
101 
102 
103 
104  /*---------------------.
105  | is_cycle_ambiguous. |
106  `---------------------*/
107 
109  template <Automaton Aut>
110  bool is_cycle_ambiguous(const Aut& aut)
111  {
112  // Find all strongly connected components.
113  const auto& coms = strong_components(aut,
115  if (getenv("VCSN_DEBUG"))
116  {
117  std::cerr << "number states of automaton: " <<
118  aut->num_states() << std::endl;
119  std::cerr << "number components: " <<
120  coms.size() << std::endl;
121  }
122 
123  // Check each component if it is cycle-ambiguous.
124  if (coms.size() == 1)
125  return is_cycle_ambiguous_scc(aut);
126  for (const auto &c : coms)
127  {
128  const auto& a = aut_of_component(c, aut);
129  if (is_cycle_ambiguous_scc(a))
130  return true;
131  }
132  return false;
133  }
134 
137  template <Automaton Aut>
138  bool is_cycle_ambiguous_scc(const Aut& aut)
139  {
140  auto prod = conjunction(aut, aut);
141  const auto& coms = strong_components(prod,
143  const auto& origins = prod->origins();
144  // In one SCC of prod = aut & aut, if there exist two states (s0,
145  // s0) (on the diagonal) and (s1, s2) with s1 != s2 (off the
146  // diagonal) then aut has two cycles with the same label:
147  // s0->s1->s0 and s0->s2->s0.
148  for (const auto& c : coms)
149  {
150  bool on = false;
151  bool off = false;
152  for (auto s : c)
153  {
154  auto p = origins.at(s);
155  if (std::get<0>(p) == std::get<1>(p))
156  on = true;
157  else
158  off = true;
159  if (on && off)
160  return true;
161  }
162  }
163  return false;
164  }
165 
166  namespace dyn
167  {
168  namespace detail
169  {
171  template <Automaton Aut>
172  bool
174  {
175  const auto& a = aut->as<Aut>();
177  }
178  }
179  }
180 }
ValueSet::value_t tuple(const ValueSet &vs, const typename ValueSets::value_t &...v)
Definition: tuple.hh:43
fresh_automaton_t_of< Aut > aut_of_component(const detail::component_t< Aut > &com, const Aut &aut)
Generate a subautomaton corresponding to an SCC.
Definition: scc.hh:573
auto conjunction(const Auts &...as) -> tuple_automaton< decltype(meet_automata(as...)), Auts... >
Build the (accessible part of the) conjunction.
Definition: conjunction.hh:448
Definition: a-star.hh:8
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
bool is_cycle_ambiguous(const Aut &aut)
Whether aut is cycle-ambiguous.
bool is_cycle_ambiguous_scc(const Aut &aut)
Whether aut is cycle-ambiguous.
filter_automaton< Aut > coaccessible(const Aut &a)
Coaccessible part of an automaton.
Definition: accessible.hh:142
auto path_monomial(const Aut &aut, const std::vector< transition_t_of< Aut >> &path, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post()) -> boost::optional< typename detail::word_polynomialset_t< context_t_of< Aut >>::monomial_t >
Given a path (typically computed by lightest_path), the corresponding monomial (label, weight).
label make_label(const LabelSet &ls, const typename LabelSet::value_t &l)
Definition: label.hh:80
bool is_cycle_ambiguous(const automaton &aut)
Bridge.
states_t< Aut > coaccessible_states(const Aut &a, bool strict=true)
The set of coaccessible states, including post(), and possibly pre().
Definition: accessible.hh:64
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
std::shared_ptr< const detail::label_base > label
Definition: fwd.hh:61
bool is_ambiguous(const automaton &aut)
Bridge.
Definition: is-ambiguous.hh:53
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:269
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
label ambiguous_word(const automaton &aut)
Bridge.
Definition: is-ambiguous.hh:93
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:82
bool is_ambiguous(const Aut &aut)
Definition: is-ambiguous.hh:41
word_t_of< Aut > ambiguous_word(const Aut &aut)
Definition: is-ambiguous.hh:66
const detail::components_t< Aut > strong_components(const Aut &aut, Tag={})
Find all strongly connected components of aut.
Definition: scc.hh:540
std::vector< transition_t_of< Aut > > lightest_path(const Aut &aut, state_t_of< Aut > source, state_t_of< Aut > dest, a_star_tag)
Definition: a-star.hh:151