Awali
Another Weighted Automata library
is_functional.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_ALGOS_IS_FUNCTIONAL_HH
18 #define AWALI_ALGOS_IS_FUNCTIONAL_HH
19 
20 # include <stack>
21 # include <unordered_map>
22 
24 //#include <awali/sttc/misc/sub-tuple.hh> // make_index_sequence
25 #include <awali/sttc/misc/add_epsilon_trans.hh> // is_epsilon
26 #include <awali/sttc/algos/projection.hh> // tuple_to_tupleset
30 
31 
32 namespace awali { namespace sttc {
33 
34  template <typename Tdc>
35  bool is_functional(Tdc& transducer)
36  {
37  auto inv = sttc::projections<1,0>(transducer);
38  auto tdc = compose(inv, transducer);
39  trim_here(tdc);
40  std::unordered_map<unsigned, std::pair<std::string,std::string>> valuations;
41  std::stack<unsigned> todo;
42 
43  std::pair<std::string,std::string> base{"",""};
44  using labelset_t = typename labelset_t_of<Tdc>::template valueset_t<1>;
45 
46  for(auto ti : tdc->initial_transitions()) {
47  //if the initial state has already been met
48  auto it1 = valuations.find(tdc->dst_of(ti));
49  if(it1 != valuations.end()) {
50  //it should have a trivial valuation
51  if(it1->second != base)
52  return false;
53  }
54  else {
55  valuations.emplace(std::make_pair(tdc->dst_of(ti),base));
56  todo.emplace(tdc->dst_of(ti));
57  }
58  while(!todo.empty()) {
59  unsigned s = todo.top();
60  todo.pop();
61  //retrieve the valuation of state s:
62  auto valuation = valuations.find(s)->second;
63  for(auto tr : tdc->all_out(s)) {
64  unsigned t = tdc->dst_of(tr);
65  if(t == tdc->post()) {
66  //if s is final it should have a trivial valuation
67  if(valuation != base)
68  return false;
69  }
70  else {
71  auto l= tdc->label_of(tr);
72  //the valuation of t is the valuation of s...
73  std::pair<std::string,std::string> t_val{valuation};
74  //... plus the label of the transition
75  if(!is_epsilon<labelset_t>(std::get<0>(l))) {
76  auto c = std::get<0>(l);
77  t_val.first = t_val.first+c;
78  }
79  if(!is_epsilon<labelset_t>(std::get<1>(l))) {
80  auto c = std::get<1>(l);
81  t_val.second = t_val.second+c;
82  }
83  //compute the length p of the greater common prefix
84  unsigned p;
85  for(p=0; p< t_val.first.length() && p<t_val.second.length() && t_val.first[p]==t_val.second[p]; ++p)
86  ;
87  //... minus the greatest common prefix
88  t_val.first = t_val.first.substr(p);
89  t_val.second = t_val.second.substr(p);
90  //at least one component of the valuation should be empty
91  if(t_val.first.length() >0 && t_val.second.length()>0)
92  return false;
93  //if t has already been met, it should have the same valuation
94  auto it2 = valuations.find(t);
95  if(it2 != valuations.end()) {
96  if(it2->second != t_val)
97  return false;
98  }
99  else {
100  valuations.emplace(std::make_pair(t,t_val));
101  todo.emplace(t);
102  }
103  }
104  }
105  }
106  }
107  return true;
108  }
109 
110 }}//end of ns awali::stc
111 
112 #endif // !AWALI_ALGOS_IS_FUNCTIONAL_HH
The semiring of complex numbers.
Definition: c.hh:44
auto compose(const TDC1 &tdc1, const TDC2 &tdc2, bool keep_history=true) -> typename internal::composer< TDC1, TDC2, 1, 0 >::automaton_t
Composition of two transducers.
Definition: compose.hh:285
void trim_here(Aut &aut)
In-place trim subautomaton.
Definition: accessible.hh:292
typename internal::labelset_t_of_impl< internal::base_t< ValueSet > >::type labelset_t_of
Helper to retrieve the type of the labelset of a value set.
Definition: traits.hh:76
bool is_functional(Tdc &transducer)
Definition: is_functional.hh:35
Main namespace of Awali.
Definition: ato.hh:22