Vcsn  2.3
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/value.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_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  // Check each component if it is cycle-ambiguous.
116  if (coms.size() == 1)
117  return is_cycle_ambiguous_scc(aut);
118  for (const auto &c : coms)
119  {
120  const auto& a = aut_of_component(c, aut);
121  if (is_cycle_ambiguous_scc(a))
122  return true;
123  }
124  return false;
125  }
126 
130  template <Automaton Aut>
131  bool is_cycle_ambiguous_scc(const Aut& aut)
132  {
133  auto prod = conjunction(aut, aut);
134  const auto& coms = strong_components(prod,
136  const auto& origins = prod->origins();
137  // In one SCC of prod = aut & aut, if there exist two states (s0,
138  // s0) (on the diagonal) and (s1, s2) with s1 != s2 (off the
139  // diagonal) then aut has two cycles with the same label:
140  // s0->s1->s0 and s0->s2->s0.
141  for (const auto& c : coms)
142  {
143  bool on = false;
144  bool off = false;
145  for (auto s : c)
146  {
147  auto p = origins.at(s);
148  if (std::get<0>(p) == std::get<1>(p))
149  on = true;
150  else
151  off = true;
152  if (on && off)
153  return true;
154  }
155  }
156  return false;
157  }
158 
159  namespace dyn
160  {
161  namespace detail
162  {
164  template <Automaton Aut>
165  bool
167  {
168  const auto& a = aut->as<Aut>();
170  }
171  }
172  }
173 }
bool is_cycle_ambiguous(const automaton &aut)
Bridge.
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:90
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:258
automaton conjunction(const automaton &lhs, const automaton &rhs, bool lazy=false)
The conjunction (aka synchronized product) of automata.
Definition: others.cc:24
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
bool is_ambiguous(const Aut &aut)
Definition: is-ambiguous.hh:41
auto tuple(const Auts &...as)
Build the (accessible part of the) tuple.
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
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
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
value_impl< detail::label_tag > label
Definition: fwd.hh:26
bool is_cycle_ambiguous_scc(const Aut &aut)
Whether aut is cycle-ambiguous.
Definition: a-star.hh:8
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
A dyn automaton.
Definition: automaton.hh:17
bool is_ambiguous(const automaton &aut)
Bridge.
Definition: is-ambiguous.hh:53
const detail::components_t< Aut > strong_components(const Aut &aut, Tag={})
Find all strongly connected components of aut.
Definition: scc.hh:540
bool is_cycle_ambiguous(const automaton &aut)
Whether the automaton is cycle-ambiguous.
label ambiguous_word(const automaton &aut)
Bridge.
Definition: is-ambiguous.hh:93
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).
auto conjunction(const Aut &aut, to exp) -> fresh_automaton_t_of< Aut >
Repeated conjunction of a automaton.
Definition: conjunction.hh:947
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
filter_automaton< Aut > coaccessible(const Aut &a)
Coaccessible part of an automaton.
Definition: accessible.hh:142
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
word_t_of< Aut > ambiguous_word(const Aut &aut)
Definition: is-ambiguous.hh:66