Vcsn  2.3
Be Rational
automatonset.hh
Go to the documentation of this file.
1 #pragma once
2 
4 #include <vcsn/algos/complete.hh>
5 #include <vcsn/algos/compose.hh>
7 #include <vcsn/algos/weight.hh>
8 #include <vcsn/algos/multiply.hh>
9 #include <vcsn/algos/proper.hh>
10 #include <vcsn/algos/add.hh>
13 #include <vcsn/ctx/context.hh>
14 
15 namespace vcsn
16 {
17 
18  template <typename Context, typename Tag>
20  {
21  public:
22  using context_t = Context;
23  using tag_t = Tag;
27  using kind_t = typename context_t::kind_t;
28 
30  using state_t = unsigned;
32  using transition_t = unsigned;
34  using label_t = typename labelset_t::value_t;
36  using weight_t = typename weightset_t::value_t;
37 
38  static symbol sname()
39  {
40  static auto res = symbol{"automatonset<" + context_t::sname()
41  + ", " + tag_t::sname() + '>'};
42  return res;
43  }
44 
46  : ctx_{c}
47  {}
48 
50  auto print_set(std::ostream& o, format fmt = {}) const
51  -> std::ostream&
52  {
53  switch (fmt.kind())
54  {
55  case format::latex:
56  o << "\\mathsf{Aut}[";
57  ctx_.print_set(o, fmt);
58  o << ", " << tag_t::sname() << ']';
59  break;
60  case format::sname:
61  o << "automatonset<";
62  ctx_.print_set(o, fmt);
63  o << ", " << tag_t::sname() << '>';
64  break;
65  case format::text:
66  case format::utf8:
67  o << "Aut[";
68  ctx_.print_set(o, fmt);
69  o << ", " << tag_t::sname() << ']';
70  break;
71  case format::raw:
72  assert(!"automatonset::print_set: invalid format: rat");
73  break;
74  }
75  return o;
76  }
77 
78  auto zero() const -> value_t
79  {
81  auto s = res->new_state();
82  res->set_initial(s);
83  return res;
84  }
85 
86  auto one() const -> value_t
87  {
89  auto s = res->new_state();
90  res->set_initial(s);
91  res->set_final(s);
92  return res;
93  }
94 
95  auto atom(const label_t& l) const -> value_t
96  {
98  auto s0 = res->new_state();
99  res->set_initial(s0);
100  auto s1 = res->new_state();
101  res->new_transition(s0, s1, l);
102  res->set_final(s1);
103  return res;
104  }
105 
106  static auto add(const value_t& l, const value_t& r) -> value_t
107  {
108  return ::vcsn::add(l, r, tag_t{});
109  }
110 
111  static auto mul(const value_t& l, const value_t& r) -> value_t
112  {
114  }
115 
117  template <typename Ctx = context_t>
118  auto compose(const value_t& l, const value_t& r) const
119  -> std::enable_if_t<are_composable<Ctx, Ctx>{}, value_t>
120  {
122  }
123 
125  auto conjunction(const value_t& l, const value_t& r) const -> value_t
126  {
127  namespace v = ::vcsn;
129  // Preserve standardness.
130  return v::is_empty(res) ? zero() : res;
131  }
132 
134  auto infiltrate(const value_t& l, const value_t& r) const -> value_t
135  {
136  return ::vcsn::infiltrate(l, r)->strip();
137  }
138 
140  auto shuffle(const value_t& l, const value_t& r) const -> value_t
141  {
142  return ::vcsn::shuffle(l, r)->strip();
143  }
144 
146  template <typename... Value>
147  auto tuple(Value&&... v) const -> value_t
148  {
149  return ::vcsn::tuple(v...)->strip();
150  }
151 
153  auto power(const value_t& e, unsigned n) const -> value_t
154  {
156  }
157 
159  auto ldivide(const value_t& l, const value_t& r) const -> value_t
160  {
161  namespace v = ::vcsn;
162  // We need a free labelset, but proper automata.
163  auto lhs = make_nullable_automaton(ctx_);
164  copy_into(v::proper(l), lhs);
165  auto rhs = make_nullable_automaton(ctx_);
166  copy_into(v::proper(r), rhs);
167 
169  // ldivide might introduce several initial states, e.g. a? \ a.
171  return v::is_empty(res) ? zero() : res;
172  }
173 
175  auto rdivide(const value_t& l, const value_t& r) const -> value_t
176  {
177  namespace v = ::vcsn;
178  // We need a free labelset, but proper automata.
179  auto lhs = make_nullable_automaton(ctx_);
180  copy_into(v::proper(l), lhs);
181  auto rhs = make_nullable_automaton(ctx_);
182  copy_into(v::proper(r), rhs);
183 
186  res);
187  return v::is_empty(res) ? zero() : res;
188  }
189 
191  auto star(const value_t& e) const -> value_t
192  {
194  }
195 
197  auto complement(const value_t& e, std::true_type) const -> value_t
198  {
199  namespace v = ::vcsn;
200  // The automaton for e does not have spontaneous transitions,
201  // but we call proper because determinize needs the labelset to
202  // be free. But then the result is free too, we might have to
203  // restore the context.
204  auto a =
206  if (v::is_empty(a))
207  return zero();
208  else
209  {
211  copy_into(a, res);
212  return res;
213  }
214  }
215 
217  auto complement(const value_t&, std::false_type) const -> value_t
218  {
219  raise("inductive: cannot complement on multitape: ", ctx_);
220  }
221 
223  auto complement(const value_t& e) const -> value_t
224  {
226  }
227 
229  auto transposition(const value_t& e) const -> value_t
230  {
231  return ::vcsn::standard(::vcsn::transpose(e)->automaton());
232  }
233 
235  auto rweight(const value_t& e, const weight_t& w) const -> value_t
236  {
237  return ::vcsn::rweight(e, w, tag_t{});
238  }
239 
241  auto lweight(const weight_t& w, const value_t& e) const -> value_t
242  {
243  return ::vcsn::lweight(w, e, tag_t{});
244  }
245 
246  protected:
248  };
249 }
return v
Definition: multiply.hh:361
auto complete(const Aut &aut) -> decltype(::vcsn::copy(aut))
Definition: complete.hh:61
variadic< type_t::add, Context > add
Definition: fwd.hh:157
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:238
variadic< type_t::ldivide, Context > ldivide
Definition: fwd.hh:148
auto complement(const value_t &, std::false_type) const -> value_t
Add a complement operator: e{c}.
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
auto complement(const value_t &e) const -> value_t
Add a complement operator: e{c}.
auto multiply(const Aut1 &lhs, const Aut2 &rhs, Tag tag={}) -> decltype(lhs->null_state(), rhs->null_state(), detail::make_join_automaton(tag, lhs, rhs))
Concatenate two automata, general case.
Definition: multiply.hh:151
auto proper(const Aut &aut, direction dir=direction::backward, bool prune=true, const std::string &algo="auto") -> fresh_automaton_t_of< Aut, detail::proper_context< context_t_of< Aut >>>
Eliminate spontaneous transitions.
Definition: proper.hh:243
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
bool is_empty(const Aut &a) ATTRIBUTE_PURE
Whether has no states.
Definition: accessible.hh:192
symbol sname()
Definition: name.hh:65
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
variadic< type_t::infiltrate, Context > infiltrate
Definition: fwd.hh:145
auto complement(const value_t &e, std::true_type) const -> value_t
Add a complement operator: e{c}.
filter_automaton< Aut > accessible(const Aut &a)
Accessible part of an automaton.
Definition: accessible.hh:134
Print as a parsable type string.
Definition: format.hh:26
auto rweight(const value_t &e, const weight_t &w) const -> value_t
Right-multiplication by a weight.
variadic< type_t::shuffle, Context > shuffle
Definition: fwd.hh:154
auto make_nullable_automaton(const Context &ctx)
auto conjunction(const value_t &l, const value_t &r) const -> value_t
Build an conjunction product: l & r.
auto print_set(std::ostream &o, format fmt={}) const -> std::ostream &
Format the description of this automatonset.
Definition: automatonset.hh:50
auto tuple(Value &&...v) const -> value_t
Build a tuple: e | f | ....
static auto mul(const value_t &l, const value_t &r) -> value_t
return res
Definition: multiply.hh:398
unsigned state_t
Lightweight state handle (or index).
Definition: automatonset.hh:30
auto tuple(const Auts &...as)
Build the (accessible part of the) tuple.
unary< type_t::star, Context > star
Definition: fwd.hh:126
weight_node< type_t::rweight, Context > rweight
Definition: fwd.hh:182
typename labelset_t::value_t label_t
Transition label.
Definition: automatonset.hh:34
auto zero() const -> value_t
Definition: automatonset.hh:78
automatonset(const context_t &c)
Definition: automatonset.hh:45
unsigned transition_t
Lightweight transition handle (or index).
Definition: automatonset.hh:32
auto atom(const label_t &l) const -> value_t
Definition: automatonset.hh:95
auto shuffle(const value_t &l, const value_t &r) const -> value_t
Build a shuffle product: l : r.
auto standard(const Aut &aut)
Definition: standard.hh:116
auto star(const value_t &e) const -> value_t
Add a star operator: e*.
Whether a ValueSet, or a context, is multitape.
Definition: tupleset.hh:1085
Definition: a-star.hh:8
auto compose(const value_t &l, const value_t &r) const -> std::enable_if_t< are_composable< Ctx, Ctx >
Build a composition: l @ r.
auto one() const -> value_t
Definition: automatonset.hh:86
An input/output format for valuesets.
Definition: format.hh:13
void copy_into(const AutIn &in, AutOut &out, KeepState keep_state, KeepTrans keep_trans)
Copy selected states and transitions of an automaton.
Definition: copy.hh:267
auto rdivide(const Aut1 &a1, const Aut2 &a2)
Compute the right quotient.
Definition: conjunction.hh:749
auto determinize(const Aut &a, Tag={}, bool_constant< Lazy >={})
Definition: determinize.hh:247
auto transposition(const value_t &e) const -> value_t
Add a transposition operator.
Print as is. For instance, don't try to escape labels.
Definition: format.hh:24
auto strip(const Aut &aut, int) -> decltype(aut->strip())
Definition: strip.hh:15
variadic< type_t::conjunction, Context > conjunction
Definition: fwd.hh:142
static auto add(const value_t &l, const value_t &r) -> value_t
Print as rich UTF-8 text, escaped.
Definition: format.hh:30
auto infiltrate(const value_t &l, const value_t &r) const -> value_t
Build an infiltration product: l &: r.
ValueSet::value_t compose(const ValueSet &vs, const typename ValueSet::value_t &lhs, const typename ValueSet::value_t &rhs)
Composition of values.
unary< type_t::complement, Context > complement
Definition: fwd.hh:123
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
weight_node< type_t::lweight, Context > lweight
Definition: fwd.hh:179
Print for LaTeX.
Definition: format.hh:22
filter_automaton< Aut > coaccessible(const Aut &a)
Coaccessible part of an automaton.
Definition: accessible.hh:142
std::integral_constant< bool, B > bool_constant
Definition: type_traits.hh:12
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
auto lweight(const weight_t &w, const value_t &e) const -> value_t
Left-multiplication by a weight.
typename weightset_t::value_t weight_t
Transition weight.
Definition: automatonset.hh:36
Print as plain (ASCII) text, escaped.
Definition: format.hh:28
static symbol sname()
Definition: automatonset.hh:38
auto power(const value_t &e, unsigned n) const -> value_t
Add a power operator: e{n}.
auto rdivide(const value_t &l, const value_t &r) const -> value_t
Build a right division: l {/} r.
auto ldivide(const value_t &l, const value_t &r) const -> value_t
r`.
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)