1 // -*- coding: utf-8 -*- 2 // Copyright (C) 2021 Laboratoire de Recherche et Développement 3 // de l'Epita (LRDE). 4 // 5 // This file is part of Spot, a model checking library. 6 // 7 // Spot is free software; you can redistribute it and/or modify it 8 // under the terms of the GNU General Public License as published by 9 // the Free Software Foundation; either version 3 of the License, or 10 // (at your option) any later version. 11 // 12 // Spot is distributed in the hope that it will be useful, but WITHOUT 13 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 14 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 15 // License for more details. 16 // 17 // You should have received a copy of the GNU General Public License 18 // along with this program. If not, see <http://www.gnu.org/licenses/>. 19 20 #include "config.h" 21 #include <spot/twaalgos/mealy_machine.hh> 22 23 #include <queue> 24 #include <deque> 25 #include <set> 26 #include <list> 27 #include <vector> 28 #include <sstream> 29 #include <string> 30 31 #include <spot/misc/bddlt.hh> 32 #include <spot/misc/hash.hh> 33 #include <spot/misc/timer.hh> 34 #include <spot/misc/minato.hh> 35 #include <spot/twaalgos/game.hh> 36 #include <spot/twaalgos/hoa.hh> 37 #include <spot/twaalgos/synthesis.hh> 38 39 #include <picosat/picosat.h> 40 41 42 //#define TRACE 43 #ifdef TRACE 44 # define trace std::cerr 45 #else 46 # define trace while (0) std::cerr 47 #endif 48 49 //#define MINTIMINGS 50 #ifdef MINTIMINGS 51 # define dotimeprint std::cerr 52 #else 53 # define dotimeprint while (0) std::cerr 54 #endif 55 56 namespace 57 { is_deterministic_(const std::vector<bdd> & ins)58 bool is_deterministic_(const std::vector<bdd>& ins) 59 { 60 const unsigned n_ins = ins.size(); 61 for (unsigned idx1 = 0; idx1 < n_ins - 1; ++idx1) 62 for (unsigned idx2 = idx1 + 1; idx2 < n_ins; ++idx2) 63 if (bdd_have_common_assignment(ins[idx1], ins[idx2])) 64 return false; 65 return true; 66 } 67 } 68 69 70 namespace spot 71 { 72 73 bool is_mealy(const const_twa_graph_ptr & m)74 is_mealy(const const_twa_graph_ptr& m) 75 { 76 if (!m->acc().is_t()) 77 { 78 trace << "is_mealy(): Mealy machines must have " 79 "true acceptance condition.\n"; 80 return false; 81 } 82 83 if (!m->get_named_prop<bdd>("synthesis-outputs")) 84 { 85 trace << "is_mealy(): \"synthesis-outputs\" not found!\n"; 86 return false; 87 } 88 89 return true; 90 } 91 92 bool is_separated_mealy(const const_twa_graph_ptr & m)93 is_separated_mealy(const const_twa_graph_ptr& m) 94 { 95 if (!is_mealy(m)) 96 return false; 97 98 auto outs = get_synthesis_outputs(m); 99 100 for (const auto& e : m->edges()) 101 if ((bdd_exist(e.cond, outs) & bdd_existcomp(e.cond, outs)) != e.cond) 102 { 103 trace << "is_separated_mealy_machine(): Edge number " 104 << m->edge_number(e) << " from " << e.src << " to " << e.dst 105 << " with " << e.cond << " is not separated!\n"; 106 return false; 107 } 108 109 return true; 110 } 111 112 bool is_split_mealy(const const_twa_graph_ptr & m)113 is_split_mealy(const const_twa_graph_ptr& m) 114 { 115 if (!is_mealy(m)) 116 return false; 117 118 if (m->get_named_prop<region_t>("state-player") == nullptr) 119 { 120 trace << "is_split_mealy(): Split mealy machine must define the named " 121 "property \"state-player\"!\n"; 122 } 123 auto sp = get_state_players(m); 124 125 if (sp.size() != m->num_states()) 126 { 127 trace << "\"state-player\" has not the same size as the " 128 "automaton!\n"; 129 return false; 130 } 131 132 if (sp[m->get_init_state_number()]) 133 { 134 trace << "is_split_mealy(): Initial state must be owned by env!\n"; 135 return false; 136 } 137 138 auto outs = get_synthesis_outputs(m); 139 140 for (const auto& e : m->edges()) 141 { 142 if (sp[e.src] == sp[e.dst]) 143 { 144 trace << "is_split_mealy(): Edge number " 145 << m->edge_number(e) << " from " << e.src << " to " << e.dst 146 << " is not alternating!\n"; 147 return false; 148 } 149 if (sp[e.src] && (bdd_exist(e.cond, outs) != bddtrue)) 150 { 151 trace << "is_split_mealy(): Edge number " 152 << m->edge_number(e) << " from " << e.src << " to " << e.dst 153 << " depends on inputs, but should be labeled by outputs!\n"; 154 return false; 155 } 156 if (!sp[e.src] && (bdd_existcomp(e.cond, outs) != bddtrue)) 157 { 158 trace << "is_split_mealy(): Edge number " 159 << m->edge_number(e) << " from " << e.src << " to " << e.dst 160 << " depends on outputs, but should be labeled by inputs!\n"; 161 return false; 162 } 163 } 164 return true; 165 } 166 167 bool is_input_deterministic_mealy(const const_twa_graph_ptr & m)168 is_input_deterministic_mealy(const const_twa_graph_ptr& m) 169 { 170 if (!is_mealy(m)) 171 return false; 172 173 const unsigned N = m->num_states(); 174 175 auto sp_ptr = m->get_named_prop<region_t>("state-player"); 176 // Unsplit mealy -> sp_ptr == nullptr 177 if (sp_ptr && !is_split_mealy(m)) 178 return false; 179 180 auto outs = get_synthesis_outputs(m); 181 182 std::vector<bdd> ins; 183 for (unsigned s = 0; s < N; ++s) 184 { 185 if (sp_ptr && (*sp_ptr)[s]) 186 continue; 187 ins.clear(); 188 for (const auto& e : m->out(s)) 189 ins.push_back(sp_ptr ? e.cond 190 : bdd_exist(e.cond, outs)); 191 if (!is_deterministic_(ins)) 192 { 193 trace << "is_input_deterministic_mealy(): State number " 194 << s << " is not input determinisc!\n"; 195 return false; 196 } 197 } 198 return true; 199 } 200 201 void split_separated_mealy_here(const twa_graph_ptr & m)202 split_separated_mealy_here(const twa_graph_ptr& m) 203 { 204 assert(is_mealy(m)); 205 206 auto output_bdd = get_synthesis_outputs(m); 207 208 struct dst_cond_color_t 209 { 210 std::pair<unsigned, int> dst_cond; 211 acc_cond::mark_t color; 212 }; 213 214 auto hasher = [](const dst_cond_color_t& dcc) noexcept 215 { 216 return dcc.color.hash() ^ pair_hash()(dcc.dst_cond); 217 }; 218 auto equal = [](const dst_cond_color_t& dcc1, 219 const dst_cond_color_t& dcc2) noexcept 220 { 221 return (dcc1.dst_cond == dcc2.dst_cond) 222 && (dcc1.color == dcc2.color); 223 }; 224 225 std::unordered_map<dst_cond_color_t, unsigned, 226 decltype(hasher), 227 decltype(equal)> player_map(m->num_edges(), 228 hasher, equal); 229 230 auto get_ps = [&](unsigned dst, const bdd& ocond, 231 acc_cond::mark_t color) 232 { 233 dst_cond_color_t key{std::make_pair(dst, ocond.id()), 234 color}; 235 auto [it, inserted] = 236 player_map.try_emplace(key, m->num_states()); 237 if (!inserted) 238 return it->second; 239 unsigned ns = m->new_state(); 240 assert(ns == it->second); 241 m->new_edge(ns, dst, ocond, color); 242 return ns; 243 }; 244 245 unsigned ne = m->edge_vector().size(); 246 for (unsigned eidx = 1; eidx < ne; ++eidx) 247 { 248 const auto& e = m->edge_storage(eidx); 249 if (e.next_succ == eidx) // dead edge 250 continue; 251 bdd incond = bdd_exist(e.cond, output_bdd); 252 bdd outcond = bdd_existcomp(e.cond, output_bdd); 253 assert(((incond&outcond) == e.cond) && "Precondition violated"); 254 // Create new state and trans 255 // this may invalidate "e". 256 unsigned new_dst = get_ps(e.dst, outcond, e.acc); 257 // redirect 258 auto& e2 = m->edge_storage(eidx); 259 e2.dst = new_dst; 260 e2.cond = incond; 261 } 262 263 auto* sp_ptr = m->get_or_set_named_prop<region_t>("state-player"); 264 265 sp_ptr->resize(m->num_states()); 266 std::fill(sp_ptr->begin(), sp_ptr->end(), false); 267 for (const auto& eit : player_map) 268 (*sp_ptr)[eit.second] = true; 269 //Done 270 } 271 272 twa_graph_ptr split_separated_mealy(const const_twa_graph_ptr & m)273 split_separated_mealy(const const_twa_graph_ptr& m) 274 { 275 assert(is_mealy((m))); 276 auto m2 = make_twa_graph(m, twa::prop_set::all()); 277 m2->copy_acceptance_of(m); 278 set_synthesis_outputs(m2, get_synthesis_outputs(m)); 279 split_separated_mealy_here(m2); 280 return m2; 281 } 282 283 twa_graph_ptr unsplit_mealy(const const_twa_graph_ptr & m)284 unsplit_mealy(const const_twa_graph_ptr& m) 285 { 286 assert(is_split_mealy(m)); 287 return unsplit_2step(m); 288 } 289 290 } 291 292 namespace 293 { 294 // Anonymous for reduce_mealy 295 using namespace spot; 296 297 // Used to get the signature of the state. 298 typedef std::vector<bdd> vector_state_bdd; 299 300 // Get the list of state for each class. 301 // Note: Use map as iter. are not invalidated by inserting new elements 302 typedef std::map<bdd, std::vector<unsigned>, 303 bdd_less_than> map_bdd_lstate; 304 305 // This part is just a copy of a part of simulation.cc only suitable for 306 // deterministic monitors. 307 class sig_calculator final 308 { 309 protected: 310 typedef std::unordered_map<bdd, bdd, bdd_hash> map_bdd_bdd; 311 int acc_vars; 312 acc_cond::mark_t all_inf_; 313 314 public: sig_calculator(twa_graph_ptr aut,bool implications)315 sig_calculator(twa_graph_ptr aut, bool implications) : a_(aut), 316 po_size_(0), 317 want_implications_(implications) 318 { 319 size_a_ = a_->num_states(); 320 // Now, we have to get the bdd which will represent the 321 // class. We register one bdd by state, because in the worst 322 // case, |Class| == |State|. 323 unsigned set_num = a_->get_dict() 324 ->register_anonymous_variables(size_a_, this); 325 326 bdd init = bdd_ithvar(set_num++); 327 328 used_var_.emplace_back(init); 329 330 // Initialize all classes to init. 331 previous_class_.resize(size_a_); 332 for (unsigned s = 0; s < size_a_; ++s) 333 previous_class_[s] = init; 334 for (unsigned i = set_num; i < set_num + size_a_ - 1; ++i) 335 free_var_.push(i); 336 337 relation_.reserve(size_a_); 338 relation_[init] = init; 339 } 340 341 // Reverse all the acceptance condition at the destruction of 342 // this object, because it occurs after the return of the 343 // function simulation. ~sig_calculator()344 virtual ~sig_calculator() 345 { 346 a_->get_dict()->unregister_all_my_variables(this); 347 } 348 349 // Update the name of the classes. update_previous_class()350 void update_previous_class() 351 { 352 auto it_bdd = used_var_.begin(); 353 354 // We run through the map bdd/list<state>, and we update 355 // the previous_class_ with the new data. 356 for (auto& p : sorted_classes_) 357 { 358 // If the signature of a state is bddfalse (no 359 // edges) the class of this state is bddfalse 360 // instead of an anonymous variable. It allows 361 // simplifications in the signature by removing a 362 // edge which has as a destination a state with 363 // no outgoing edge. 364 if (p->first == bddfalse) 365 for (unsigned s : p->second) 366 previous_class_[s] = bddfalse; 367 else 368 for (unsigned s : p->second) 369 previous_class_[s] = *it_bdd; 370 ++it_bdd; 371 } 372 } 373 main_loop()374 void main_loop() 375 { 376 unsigned int nb_partition_before = 0; 377 unsigned int nb_po_before = po_size_ - 1; 378 379 while (nb_partition_before != bdd_lstate_.size() 380 || nb_po_before != po_size_) 381 { 382 update_previous_class(); 383 nb_partition_before = bdd_lstate_.size(); 384 nb_po_before = po_size_; 385 po_size_ = 0; 386 update_sig(); 387 go_to_next_it(); 388 } 389 update_previous_class(); 390 } 391 392 // Take a state and compute its signature. compute_sig(unsigned src)393 bdd compute_sig(unsigned src) 394 { 395 bdd res = bddfalse; 396 397 for (auto& t : a_->out(src)) 398 { 399 // to_add is a conjunction of the acceptance condition, 400 // the label of the edge and the class of the 401 // destination and all the class it implies. 402 bdd to_add = t.cond & relation_[previous_class_[t.dst]]; 403 404 res |= to_add; 405 } 406 return res; 407 } 408 update_sig()409 void update_sig() 410 { 411 bdd_lstate_.clear(); 412 sorted_classes_.clear(); 413 for (unsigned s = 0; s < size_a_; ++s) 414 { 415 bdd sig = compute_sig(s); 416 auto p = bdd_lstate_.emplace(std::piecewise_construct, 417 std::forward_as_tuple(sig), 418 std::forward_as_tuple(1, s)); 419 if (p.second) 420 sorted_classes_.emplace_back(p.first); 421 else 422 p.first->second.emplace_back(s); 423 } 424 } 425 426 // This method renames the color set, updates the partial order. go_to_next_it()427 void go_to_next_it() 428 { 429 int nb_new_color = bdd_lstate_.size() - used_var_.size(); 430 431 // If we have created more partitions, we need to use more 432 // variables. 433 for (int i = 0; i < nb_new_color; ++i) 434 { 435 assert(!free_var_.empty()); 436 used_var_.emplace_back(bdd_ithvar(free_var_.front())); 437 free_var_.pop(); 438 } 439 440 // If we have reduced the number of partition, we 'free' them 441 // in the free_var_ list. 442 for (int i = 0; i > nb_new_color; --i) 443 { 444 assert(!used_var_.empty()); 445 free_var_.push(bdd_var(used_var_.front())); 446 used_var_.pop_front(); 447 } 448 449 assert((bdd_lstate_.size() == used_var_.size()) 450 || (bdd_lstate_.find(bddfalse) != bdd_lstate_.end() 451 && bdd_lstate_.size() == used_var_.size() + 1)); 452 453 // This vector links the tuple "C^(i-1), N^(i-1)" to the 454 // new class coloring for the next iteration. 455 std::vector<std::pair<bdd, bdd>> now_to_next; 456 unsigned sz = bdd_lstate_.size(); 457 now_to_next.reserve(sz); 458 459 auto it_bdd = used_var_.begin(); 460 461 for (auto& p : sorted_classes_) 462 { 463 // If the signature of a state is bddfalse (no edges) the 464 // class of this state is bddfalse instead of an anonymous 465 // variable. It allows simplifications in the signature by 466 // removing an edge which has as a destination a state 467 // with no outgoing edge. 468 bdd acc = bddfalse; 469 if (p->first != bddfalse) 470 acc = *it_bdd; 471 now_to_next.emplace_back(p->first, acc); 472 ++it_bdd; 473 } 474 475 // Update the partial order. 476 477 // This loop follows the pattern given by the paper. 478 // foreach class do 479 // | foreach class do 480 // | | update po if needed 481 // | od 482 // od 483 484 for (unsigned n = 0; n < sz; ++n) 485 { 486 bdd n_sig = now_to_next[n].first; 487 bdd n_class = now_to_next[n].second; 488 if (want_implications_) 489 for (unsigned m = 0; m < sz; ++m) 490 { 491 if (n == m) 492 continue; 493 if (bdd_implies(n_sig, now_to_next[m].first)) 494 { 495 n_class &= now_to_next[m].second; 496 ++po_size_; 497 } 498 } 499 relation_[now_to_next[n].second] = n_class; 500 } 501 } 502 503 // The list of states for each class at the current_iteration. 504 // Computed in `update_sig'. 505 map_bdd_lstate bdd_lstate_; 506 507 protected: 508 // The automaton which is reduced. 509 twa_graph_ptr a_; 510 511 // Implications between classes. 512 map_bdd_bdd relation_; 513 514 // Represent the class of each state at the previous iteration. 515 vector_state_bdd previous_class_; 516 517 // The above map, sorted by states number instead of BDD 518 // identifier to avoid non-determinism while iterating over all 519 // states. 520 std::vector<map_bdd_lstate::const_iterator> sorted_classes_; 521 522 // The queue of free bdd. They will be used as the identifier 523 // for the class. 524 std::queue<int> free_var_; 525 526 // The list of used bdd. They are in used as identifier for class. 527 std::deque<bdd> used_var_; 528 529 // Size of the automaton. 530 unsigned int size_a_; 531 532 // Used to know when there is no evolution in the partial order. 533 unsigned int po_size_; 534 535 // Whether to compute implications between classes. This is costly 536 // and useless when we want to recognize the same language. 537 bool want_implications_; 538 }; 539 540 // An acyclic digraph such that there is an edge q1 -> q2 if 541 // q1.label_ ⇒ q2.label_ 542 class bdd_digraph 543 { 544 private: 545 bdd label_; 546 unsigned state_; 547 std::vector<std::shared_ptr<bdd_digraph>> children_; 548 549 public: bdd_digraph()550 bdd_digraph() : label_(bddtrue), state_(-1U) {} 551 bdd_digraph(bdd label,unsigned state)552 bdd_digraph(bdd label, unsigned state) : label_(label), state_(state) {} 553 554 void all_children_aux_(std::set<std::shared_ptr<bdd_digraph>> & res)555 all_children_aux_(std::set<std::shared_ptr<bdd_digraph>>& res) 556 { 557 for (auto c : children_) 558 if (res.insert(c).second) 559 c->all_children_aux_(res); 560 } 561 562 std::set<std::shared_ptr<bdd_digraph>> all_children()563 all_children() 564 { 565 std::set<std::shared_ptr<bdd_digraph>> res; 566 all_children_aux_(res); 567 return res; 568 } 569 570 void add_aux_(std::shared_ptr<bdd_digraph> & new_node,std::vector<bool> & done)571 add_aux_(std::shared_ptr<bdd_digraph>& new_node, std::vector<bool>& done) 572 { 573 // Avoid doing twice the same state 574 if (state_ != -1U) 575 done[state_] = true; 576 for (auto& ch : children_) 577 { 578 if (done[ch->state_]) 579 continue; 580 if (bdd_implies(new_node->label_, ch->label_)) 581 ch->add_aux_(new_node, done); 582 else if (bdd_implies(ch->label_, new_node->label_)) 583 { 584 auto ch_nodes = ch->all_children(); 585 new_node->children_.push_back(ch); 586 for (auto& x : ch_nodes) 587 new_node->children_.push_back(x); 588 } 589 } 590 assert(bdd_implies(new_node->label_, label_)); 591 children_.push_back(new_node); 592 } 593 594 void add(std::shared_ptr<bdd_digraph> & new_node,bool rec,unsigned max_state)595 add(std::shared_ptr<bdd_digraph>& new_node, bool rec, 596 unsigned max_state) 597 { 598 if (new_node->label_ == bddtrue) 599 { 600 assert(label_ == bddtrue); 601 state_ = new_node->state_; 602 return; 603 } 604 if (rec) 605 { 606 std::vector<bool> done(max_state, false); 607 add_aux_(new_node, done); 608 } 609 else 610 children_.push_back(new_node); 611 } 612 613 unsigned flatten_aux(std::unordered_map<bdd,unsigned,spot::bdd_hash> & res)614 flatten_aux(std::unordered_map<bdd, unsigned, spot::bdd_hash>& res) 615 { 616 if (children_.empty()) 617 { 618 res.insert({label_, state_}); 619 return state_; 620 } 621 auto ch_size = children_.size(); 622 unsigned pos = ch_size - 1; 623 auto my_repr = children_[pos]->flatten_aux(res); 624 res.insert({label_, my_repr}); 625 for (unsigned i = 0; i < ch_size; ++i) 626 { 627 if (i == pos) 628 continue; 629 children_[i]->flatten_aux(res); 630 } 631 return my_repr; 632 } 633 634 std::unordered_map<bdd, unsigned, spot::bdd_hash> flatten()635 flatten() 636 { 637 std::unordered_map<bdd, unsigned, spot::bdd_hash> res; 638 flatten_aux(res); 639 return res; 640 } 641 642 // Transforms children_ such that the child with the higher use_count() is 643 // at the end. 644 void sort_nodes()645 sort_nodes() 646 { 647 if (!children_.empty()) 648 { 649 auto max_pos = std::max_element(children_.begin(), children_.end(), 650 [](const std::shared_ptr<bdd_digraph>& n1, 651 const std::shared_ptr<bdd_digraph>& n2) 652 { 653 return n1.use_count() < n2.use_count(); 654 }); 655 std::iter_swap(max_pos, children_.end() - 1); 656 } 657 } 658 }; 659 660 661 // Associate to a state a representative. The first value of the result 662 // is -1U if ∀i repr[i] = i 663 std::vector<unsigned> get_repres(twa_graph_ptr & a,bool rec)664 get_repres(twa_graph_ptr& a, bool rec) 665 { 666 const auto a_num_states = a->num_states(); 667 668 std::vector<unsigned> repr(a_num_states); 669 bdd_digraph graph; 670 std::vector<bdd> signatures(a_num_states); 671 sig_calculator red(a, rec); 672 red.main_loop(); 673 if (!rec && red.bdd_lstate_.size() == a_num_states) 674 { 675 repr[0] = -1U; 676 return repr; 677 } 678 for (auto& [sig, states] : red.bdd_lstate_) 679 { 680 assert(!states.empty()); 681 bool in_tree = false; 682 for (auto state : states) 683 { 684 signatures[state] = sig; 685 // If it is not the first iteration, le BDD is already in the graph. 686 if (!in_tree) 687 { 688 in_tree = true; 689 auto new_node = 690 std::make_shared<bdd_digraph>(bdd_digraph(sig, state)); 691 graph.add(new_node, rec, a_num_states); 692 } 693 } 694 } 695 graph.sort_nodes(); 696 auto repr_map = graph.flatten(); 697 698 bool is_useless_map = true; 699 for (unsigned i = 0; i < a_num_states; ++i) 700 { 701 repr[i] = repr_map[signatures[i]]; 702 is_useless_map &= (repr[i] == i); 703 } 704 705 if (is_useless_map) 706 { 707 repr[0] = -1U; 708 return repr; 709 } 710 return repr; 711 } 712 } 713 714 namespace spot 715 { reduce_mealy(const const_twa_graph_ptr & mm,bool output_assignment)716 twa_graph_ptr reduce_mealy(const const_twa_graph_ptr& mm, 717 bool output_assignment) 718 { 719 assert(is_mealy(mm)); 720 if (mm->get_named_prop<std::vector<bool>>("state-player")) 721 throw std::runtime_error("reduce_mealy(): " 722 "Only works on unsplit machines.\n"); 723 724 auto mmc = make_twa_graph(mm, twa::prop_set::all()); 725 mmc->copy_ap_of(mm); 726 mmc->copy_acceptance_of(mm); 727 set_synthesis_outputs(mmc, get_synthesis_outputs(mm)); 728 729 reduce_mealy_here(mmc, output_assignment); 730 731 assert(is_mealy(mmc)); 732 return mmc; 733 } 734 reduce_mealy_here(twa_graph_ptr & mm,bool output_assignment)735 void reduce_mealy_here(twa_graph_ptr& mm, bool output_assignment) 736 { 737 assert(is_mealy(mm)); 738 739 // Only consider infinite runs 740 mm->purge_dead_states(); 741 742 auto repr = get_repres(mm, output_assignment); 743 if (repr[0] == -1U) 744 return; 745 746 // Change the destination of transitions using a DFT to avoid useless 747 // modifications. 748 auto init = repr[mm->get_init_state_number()]; 749 mm->set_init_state(init); 750 std::stack<unsigned> todo; 751 std::vector<bool> done(mm->num_states(), false); 752 todo.emplace(init); 753 while (!todo.empty()) 754 { 755 auto current = todo.top(); 756 todo.pop(); 757 done[current] = true; 758 for (auto& e : mm->out(current)) 759 { 760 auto repr_dst = repr[e.dst]; 761 e.dst = repr_dst; 762 if (!done[repr_dst]) 763 todo.emplace(repr_dst); 764 } 765 } 766 mm->purge_unreachable_states(); 767 assert(is_mealy(mm)); 768 } 769 } 770 771 // Anonymous for mealy_min 772 namespace 773 { 774 using namespace spot; 775 776 // helper 777 #ifdef TRACE trace_clause(const std::vector<int> & clause)778 void trace_clause(const std::vector<int>& clause) 779 { 780 auto it = clause.begin(); 781 if (*it == 0) 782 throw std::runtime_error("Trivially false clause"); 783 for (; it != clause.end(); ++it) 784 { 785 trace << *it << ' '; 786 if (*it == 0) 787 { 788 trace << '\n'; 789 break; 790 } 791 } 792 assert(it != clause.end() && "Clause must be zero terminated."); 793 } 794 #else trace_clause(const std::vector<int> &)795 void trace_clause(const std::vector<int>&){} 796 #endif 797 798 template <class CONT> all_of(const CONT & c)799 bool all_of(const CONT& c) 800 { 801 return std::all_of(c.begin(), c.end(), [](const auto& e){return e; }); 802 } 803 template <class CONT, class FUN> all_of(const CONT & c,FUN fun)804 bool all_of(const CONT& c, FUN fun) 805 { 806 return std::all_of(c.begin(), c.end(), fun); 807 } 808 809 template <class CONT> find_first_index_of(const CONT & c)810 size_t find_first_index_of(const CONT& c) 811 { 812 size_t s = c.size(); 813 for (unsigned i = 0; i < s; ++i) 814 if (c[i]) 815 return i; 816 return s + 1; 817 } 818 template <class CONT, class PRED> find_first_index_of(const CONT & c,PRED pred)819 size_t find_first_index_of(const CONT& c, PRED pred) 820 { 821 const size_t s = c.size(); 822 for (unsigned i = 0; i < s; ++i) 823 if (pred(c[i])) 824 return i; 825 return s; 826 } 827 828 // key for multimap 829 // Attention when working with signed integers: Then this will not be good 830 // in general. It works well with literals (ints) as they are positive 831 // in their normal form 832 struct 833 id_cont_hasher 834 { 835 template<class CONT> operator ()__anonff402b370711::id_cont_hasher836 size_t operator()(const CONT& v) const 837 { 838 839 if constexpr (sizeof(typename CONT::value_type) <= sizeof(size_t)/2) 840 { 841 constexpr size_t shift_val1 = 842 sizeof(typename CONT::value_type)*CHAR_BIT/2; 843 constexpr size_t shift_val2 = (shift_val1*2)/3; 844 845 size_t vs = v.size(); 846 switch (vs) 847 { 848 case 0: 849 return 0; 850 case 1: 851 return (size_t) *v.begin(); 852 case 2: 853 { 854 auto it = v.begin(); 855 return (((size_t) *it)<<shift_val1) + (size_t) *(++it); 856 } 857 default: 858 { 859 size_t h = wang32_hash(vs); 860 size_t hh; 861 auto it = v.begin(); 862 const auto it_end = v.end(); 863 do 864 { 865 hh = (size_t) *it; 866 hh <<= shift_val2; 867 ++it; 868 if (it != it_end) 869 { 870 hh += (size_t) *it; 871 hh <<= shift_val2; 872 ++it; 873 if (it != it_end) 874 { 875 hh += (size_t) *it; 876 ++it; 877 } 878 } 879 h ^= wang32_hash(hh); 880 } while (it != it_end); 881 return h; 882 } 883 } 884 } 885 else 886 { 887 //Implementation for less frequent type sizes is less efficient 888 size_t h = wang32_hash(v.size()); 889 for (auto e : v) 890 h ^= wang32_hash(e); 891 return h; 892 } 893 } 894 }; 895 896 897 // A class representing a square matrix 898 template<class T, bool is_sym> 899 class square_matrix: private std::vector<T> 900 { 901 private: 902 size_t dim_; 903 904 public: square_matrix()905 square_matrix() 906 : std::vector<T>() 907 , dim_(0) 908 {} 909 square_matrix(size_t dim)910 square_matrix(size_t dim) 911 : std::vector<T>(dim*dim) 912 , dim_{dim} 913 {} 914 square_matrix(size_t dim,const T & t)915 square_matrix(size_t dim, const T& t) 916 : std::vector<T>(dim*dim, t) 917 , dim_{dim} 918 {} 919 920 using typename std::vector<T>::value_type; 921 using typename std::vector<T>::size_type; 922 using typename std::vector<T>::difference_type; 923 using typename std::vector<T>::iterator; 924 using typename std::vector<T>::const_iterator; 925 dim() const926 inline size_t dim() const 927 { 928 return dim_; 929 } 930 // i: row number 931 // j: column number 932 // Stored in row major idx_(size_t i,size_t j) const933 inline size_t idx_(size_t i, size_t j) const 934 { 935 return i * dim_ + j; 936 } idx(size_t i,size_t j) const937 inline size_t idx(size_t i, size_t j) const 938 { 939 #ifndef NDEBUG 940 if (i >= dim_) 941 throw std::runtime_error("i exceeds dim"); 942 if (j >= dim_) 943 throw std::runtime_error("j exceeds dim"); 944 #endif 945 return idx_(i, j); 946 } 947 set(size_t i,size_t j,const T & t)948 void set(size_t i, size_t j, const T& t) 949 { 950 (*this)[idx(i, j)] = t; 951 if constexpr (is_sym) 952 (*this)[idx(j, i)] = t; 953 } get(size_t i,size_t j) const954 T get(size_t i, size_t j) const 955 { 956 return (*this)[idx(i, j)]; 957 } 958 get_cline(size_t i) const959 std::pair<const_iterator, const_iterator> get_cline(size_t i) const 960 { 961 assert(i < dim_); 962 return {cbegin() + idx(i, 0), cbegin() + idx_(i+1, 0)}; 963 } get_line(size_t i)964 std::pair<iterator, iterator> get_line(size_t i) 965 { 966 assert(i < dim_); 967 return {begin() + idx(i, 0), begin() + idx_(i+1, 0)}; 968 } 969 get_cline_begin(size_t i) const970 const_iterator get_cline_begin(size_t i) const 971 { 972 assert(i < dim_); 973 return cbegin() + idx(i, 0); 974 } get_line_begin(size_t i)975 iterator get_line_begin(size_t i) 976 { 977 assert(i < dim_); 978 return begin() + idx(i, 0); 979 } get_cline_end(size_t i) const980 const_iterator get_cline_end(size_t i) const 981 { 982 assert(i < dim_); 983 return cbegin() + idx(i+1, 0); 984 } get_line_end(size_t i)985 iterator get_line_end(size_t i) 986 { 987 assert(i < dim_); 988 return begin() + idx(i+1, 0); 989 } 990 using std::vector<T>::begin; 991 using std::vector<T>::cbegin; 992 using std::vector<T>::end; 993 using std::vector<T>::cend; 994 print(std::ostream & o) const995 std::ostream& print(std::ostream& o) const 996 { 997 for (size_t i = 0; i < dim_; ++i) 998 { 999 for (size_t j = 0; j < dim_; ++j) 1000 o << (int) get(i, j) << ' '; 1001 o << std::endl; 1002 } 1003 return o; 1004 } 1005 }; 1006 1007 std::pair<const_twa_graph_ptr, unsigned> reorganize_mm(const_twa_graph_ptr mm,const std::vector<bool> & sp)1008 reorganize_mm(const_twa_graph_ptr mm, const std::vector<bool>& sp) 1009 { 1010 // Purge unreachable and reorganize the graph 1011 std::vector<unsigned> renamed(mm->num_states(), -1u); 1012 const unsigned n_old = mm->num_states(); 1013 unsigned next_env = 0; 1014 unsigned next_player = n_old; 1015 1016 std::deque<unsigned> todo; 1017 todo.push_back(mm->get_init_state_number()); 1018 renamed[todo.front()] = sp[todo.front()] ? (next_player++) 1019 : (next_env++); 1020 1021 while (!todo.empty()) 1022 { 1023 unsigned s = todo.front(); 1024 todo.pop_front(); 1025 1026 for (const auto& e : mm->out(s)) 1027 if (renamed[e.dst] == -1u) 1028 { 1029 renamed[e.dst] = sp[e.dst] ? (next_player++) 1030 : (next_env++); 1031 todo.push_back(e.dst); 1032 } 1033 } 1034 // Adjust player number 1035 const unsigned n_env = next_env; 1036 const unsigned diff = n_old - n_env; 1037 for (auto& s : renamed) 1038 s -= ((s >= n_old) && (s != -1u))*diff; 1039 const unsigned n_new 1040 = n_old - std::count(renamed.begin(), renamed.end(), -1u); 1041 1042 auto omm = make_twa_graph(mm->get_dict()); 1043 omm->copy_ap_of(mm); 1044 omm->new_states(n_new); 1045 1046 for (const auto& e : mm->edges()) 1047 { 1048 const unsigned n_src = renamed[e.src]; 1049 const unsigned n_dst = renamed[e.dst]; 1050 if (n_src != -1u && n_dst != -1u) 1051 omm->new_edge(n_src, n_dst, e.cond); 1052 } 1053 1054 std::vector<bool> spnew(n_new, true); 1055 std::fill(spnew.begin(), spnew.begin()+n_env, false); 1056 set_state_players(omm, std::move(spnew)); 1057 set_synthesis_outputs(omm, get_synthesis_outputs(mm)); 1058 1059 // Make sure we have a proper strategy, 1060 // that is each player state has only one successor 1061 assert([&]() 1062 { 1063 unsigned n_tot = omm->num_states(); 1064 for (unsigned s = n_env; s < n_tot; ++s) 1065 { 1066 auto oute = omm->out(s); 1067 if ((++oute.begin()) != oute.end()) 1068 return false; 1069 } 1070 return true; 1071 }() && "Player states have multiple edges."); 1072 1073 #ifdef TRACE 1074 trace << "State reorganize mapping\n"; 1075 for (unsigned s = 0; s < renamed.size(); ++s) 1076 trace << s << " -> " << renamed[s] << '\n'; 1077 #endif 1078 return std::make_pair(omm, n_env); 1079 } 1080 1081 square_matrix<bool, true> compute_incomp(const_twa_graph_ptr mm,const unsigned n_env,stopwatch & sw)1082 compute_incomp(const_twa_graph_ptr mm, const unsigned n_env, 1083 stopwatch& sw) 1084 { 1085 const unsigned n_tot = mm->num_states(); 1086 1087 // Final result 1088 square_matrix<bool, true> inc_env(n_env, false); 1089 1090 // Helper 1091 // Have two states already been checked for common pred 1092 square_matrix<bool, true> checked_pred(n_env, false); 1093 1094 // We also need a transposed_graph 1095 auto mm_t = make_twa_graph(mm->get_dict()); 1096 mm_t->copy_ap_of(mm); 1097 mm_t->new_states(n_env); 1098 1099 for (unsigned s = 0; s < n_env; ++s) 1100 { 1101 for (const auto& e_env : mm->out(s)) 1102 { 1103 unsigned dst_env = mm->out(e_env.dst).begin()->dst; 1104 mm_t->new_edge(dst_env, s, e_env.cond); 1105 } 1106 } 1107 1108 // Utility function 1109 auto get_cond = [&mm](unsigned s)->const bdd& 1110 {return mm->out(s).begin()->cond; }; 1111 1112 // Computing the incompatible player states 1113 1114 // todo Tradeoff: lookup in the map is usually slower, but 1115 // if it is significantly smaller, it is still worth it? 1116 // We want the matrix for faster checks later on, 1117 // but it is beneficial to first compute the 1118 // compatibility between the conditions as there might be fewer 1119 std::unordered_map<std::pair<unsigned, unsigned>, bool, pair_hash> 1120 cond_comp; 1121 // Associated condition and id of each player state 1122 std::vector<std::pair<bdd, unsigned>> ps2c; 1123 ps2c.reserve(n_tot - n_env); 1124 std::unordered_map<unsigned, unsigned> all_out_cond; 1125 for (unsigned s1 = n_env; s1 < n_tot; ++s1) 1126 { 1127 const bdd &c1 = get_cond(s1); 1128 const unsigned c1id = (unsigned)c1.id(); 1129 const auto& [it, inserted] = 1130 all_out_cond.try_emplace(c1id, all_out_cond.size()); 1131 ps2c.emplace_back(c1, it->second); 1132 #ifdef TRACE 1133 if (inserted) 1134 trace << "Register oc " << it->first << ", " << it->second 1135 << " for state " << s1 << '\n'; 1136 #endif 1137 } 1138 // Are two player condition ids states incompatible 1139 square_matrix<bool, true> inc_player(all_out_cond.size(), false); 1140 // Compute. First is id of bdd 1141 for (const auto& p1 : all_out_cond) 1142 for (const auto& p2 : all_out_cond) 1143 { 1144 if (p1.second > p2.second) 1145 continue; 1146 inc_player.set(p1.second, p2.second, 1147 !bdd_have_common_assignment( 1148 bdd_from_int((int) p1.first), 1149 bdd_from_int((int) p2.first))); 1150 assert(inc_player.get(p1.second, p2.second) 1151 == ((bdd_from_int((int) p1.first) 1152 & bdd_from_int((int) p2.first)) == bddfalse)); 1153 } 1154 auto is_p_incomp = [&](unsigned s1, unsigned s2) 1155 { 1156 return inc_player.get(ps2c[s1].second, ps2c[s2].second); 1157 }; 1158 1159 dotimeprint << "Done computing player incomp " << sw.stop() << '\n'; 1160 1161 #ifdef TRACE 1162 trace << "player cond id incomp\n"; 1163 for (const auto& elem : all_out_cond) 1164 trace << elem.second << " - " << bdd_from_int((int) elem.first) << '\n'; 1165 inc_player.print(std::cerr); 1166 #endif 1167 // direct incomp: Two env states can reach incompatible player states 1168 // under the same input 1169 auto direct_incomp = [&](unsigned s1, unsigned s2) 1170 { 1171 for (const auto& e1 : mm->out(s1)) 1172 for (const auto& e2 : mm->out(s2)) 1173 { 1174 if (!is_p_incomp(e1.dst - n_env, e2.dst - n_env)) 1175 continue; //Compatible -> no prob 1176 // Reachable under same letter? 1177 if (bdd_have_common_assignment(e1.cond, e2.cond)) 1178 { 1179 trace << s1 << " and " << s2 << " directly incomp " 1180 "due to successors " << e1.dst << " and " << e2.dst 1181 << '\n'; 1182 return true; 1183 } 1184 } 1185 return false; 1186 }; 1187 1188 // If two states can reach an incompatible state 1189 // under the same input, then they are incompatible as well 1190 auto tag_predec = [&](unsigned s1, unsigned s2) 1191 { 1192 static std::vector<std::pair<unsigned, unsigned>> todo_; 1193 assert(todo_.empty()); 1194 1195 todo_.emplace_back(s1, s2); 1196 1197 while (!todo_.empty()) 1198 { 1199 auto [i, j] = todo_.back(); 1200 todo_.pop_back(); 1201 if (checked_pred.get(i, j)) 1202 continue; 1203 // If predecs are already marked incomp 1204 for (const auto& ei : mm_t->out(i)) 1205 for (const auto& ej : mm_t->out(j)) 1206 { 1207 if (inc_env.get(ei.dst, ej.dst)) 1208 // Have already been treated 1209 continue; 1210 // Now we need to actually check it 1211 if (bdd_have_common_assignment(ei.cond, ej.cond)) 1212 { 1213 trace << ei.dst << " and " << ej.dst << " tagged incomp" 1214 " due to " << i << " and " << j << '\n'; 1215 inc_env.set(ei.dst, ej.dst, true); 1216 todo_.emplace_back(ei.dst, ej.dst); 1217 } 1218 } 1219 checked_pred.set(i, j, true); 1220 } 1221 // Done tagging all pred 1222 }; 1223 1224 for (unsigned s1 = 0; s1 < n_env; ++s1) 1225 for (unsigned s2 = s1 + 1; s2 < n_env; ++s2) 1226 { 1227 if (inc_env.get(s1, s2)) 1228 continue; // Already done 1229 // Check if they are incompatible for some letter 1230 // We have to check all pairs of edges 1231 if (direct_incomp(s1, s2)) 1232 { 1233 inc_env.set(s1, s2, true); 1234 tag_predec(s1, s2); 1235 } 1236 } 1237 1238 #ifdef TRACE 1239 trace << "Env state incomp\n"; 1240 inc_env.print(std::cerr); 1241 #endif 1242 1243 return inc_env; 1244 } 1245 1246 struct part_sol_t 1247 { 1248 std::vector<unsigned> psol; 1249 std::vector<unsigned> is_psol; 1250 std::vector<unsigned> incompvec; 1251 }; 1252 1253 // Partial solution: List of pairwise incompatible states. 1254 // Each of these states will be associated to a class. 1255 // It becomes the founding state of this class and has to belong to it get_part_sol(const square_matrix<bool,true> & incompmat)1256 part_sol_t get_part_sol(const square_matrix<bool, true>& incompmat) 1257 { 1258 // Use the "most" incompatible states as partial sol 1259 unsigned n_states = incompmat.dim(); 1260 std::vector<std::pair<unsigned, unsigned>> incompvec(n_states); 1261 1262 // square_matrix is row major! 1263 for (size_t ns = 0; ns < n_states; ++ns) 1264 { 1265 auto line_it = incompmat.get_cline(ns); 1266 incompvec[ns] = {ns, 1267 std::count(line_it.first, 1268 line_it.second, 1269 true)}; 1270 } 1271 1272 // Sort in reverse order 1273 std::sort(incompvec.begin(), incompvec.end(), 1274 [](const auto& p1, const auto& p2) 1275 {return p1.second > p2.second; }); 1276 1277 part_sol_t part_sol; 1278 auto& psol = part_sol.psol; 1279 // Add states that are incompatible with ALL states in part_sol 1280 for (auto& p : incompvec) 1281 { 1282 auto ns = p.first; 1283 if (std::all_of(psol.begin(), psol.end(), 1284 [&](auto npart) 1285 { 1286 return incompmat.get(ns, npart); 1287 })) 1288 psol.push_back(ns); 1289 } 1290 // Note: this is important for look-up later on 1291 std::sort(psol.begin(), psol.end()); 1292 part_sol.is_psol = std::vector<unsigned>(n_states, -1u); 1293 { 1294 unsigned counter = 0; 1295 for (auto s : psol) 1296 part_sol.is_psol[s] = counter++; 1297 } 1298 1299 // Also store the states in their compatibility order 1300 part_sol.incompvec.resize(n_states); 1301 std::transform(incompvec.begin(), incompvec.end(), 1302 part_sol.incompvec.begin(), 1303 [](auto& p){return p.first; }); 1304 #ifdef TRACE 1305 std::cerr << "partsol\n"; 1306 for (auto e : psol) 1307 std::cerr << e << ' '; 1308 std::cerr << "\nAssociated classes\n"; 1309 for (unsigned e : part_sol.is_psol) 1310 std::cerr << (e == -1u ? -1 : (int) e) << ' '; 1311 std::cerr << '\n'; 1312 #endif 1313 return part_sol; 1314 } 1315 1316 struct reduced_alphabet_t 1317 { 1318 unsigned n_groups; 1319 std::vector<unsigned> which_group; 1320 std::vector<std::vector<bdd>> universal_letters; //todo 1321 // minimal_letters: 1322 // Letters which can represent other letters 1323 // bdd: letter 1324 // associated set[0]: list of bdd ids which are implied by the letter 1325 // and that occur in the actual graph 1326 // associated set[1]: list of bdd ids corresponding to the covered letters 1327 // and which are represented by this one 1328 std::vector< 1329 std::unordered_map< 1330 bdd, std::pair<std::set<int>, std::set<int>>, bdd_hash>> 1331 minimal_letters; 1332 // In the sat problem, the minimal letters are simply enumerated 1333 // in the same order as the in vector below 1334 std::vector<std::vector<bdd>> minimal_letters_vec; 1335 1336 // Bisimilar vector: a letter representing multiple 1337 // minimal letters 1338 // Store the indices fo bisimilar letters 1339 // First one is the representative 1340 std::vector<std::vector<std::vector<unsigned>>> bisim_letters; 1341 1342 // all_letters: 1343 // bdd: letter 1344 // associated set: list of bdd ids which are implied by the letter 1345 // and that occur in the actual graph 1346 std::vector<std::vector<std::pair<bdd, std::set<int>>>> all_letters; 1347 1348 // Indicator if two groups share the same alphabet 1349 // group uses the alphabet of share_sigma_with[group] 1350 // We make copies as the memory gained is small compared to the 1351 // code overhead 1352 std::vector<unsigned> share_sigma_with; 1353 std::vector<unsigned> share_bisim_with; 1354 // all_min_letters 1355 // Set of all minimal letters, ignoring their respective groups 1356 unsigned n_red_sigma; 1357 }; 1358 1359 // Computes the "transitive closure of compatibility" 1360 // Only states that are transitively compatible need to 1361 // agree on the letters 1362 std::pair<unsigned, std::vector<unsigned>> trans_comp_classes(const square_matrix<bool,true> & incompmat)1363 trans_comp_classes(const square_matrix<bool, true>& incompmat) 1364 { 1365 const unsigned n_env = incompmat.dim(); 1366 1367 std::vector<unsigned> which_group(n_env, -1u); 1368 1369 std::vector<unsigned> stack_; 1370 1371 unsigned n_group = 0; 1372 for (unsigned s = 0; s < n_env; ++s) 1373 { 1374 if (which_group[s] != -1u) 1375 continue; 1376 1377 which_group[s] = n_group; 1378 1379 stack_.emplace_back(s); 1380 1381 while (!stack_.empty()) 1382 { 1383 unsigned sc = stack_.back(); 1384 stack_.pop_back(); 1385 1386 for (unsigned scp = s + 1; scp < n_env; ++scp) 1387 { 1388 if (which_group[scp] != -1u || incompmat.get(sc, scp)) 1389 continue; 1390 which_group[scp] = n_group; 1391 stack_.push_back(scp); 1392 } 1393 } 1394 ++n_group; 1395 } 1396 #ifdef TRACE 1397 trace << "We found " << n_group << " groups.\n"; 1398 for (unsigned s = 0; s < n_env; ++s) 1399 trace << s << " : " << which_group.at(s) << '\n'; 1400 #endif 1401 return std::make_pair(n_group, which_group); 1402 } 1403 1404 // Computes the letters of each group 1405 // Letters here means bdds such that for all valid 1406 // assignments of the bdd we go to the same dst from the same source compute_all_letters(reduced_alphabet_t & red,const_twa_graph_ptr & mmw,const unsigned n_env)1407 void compute_all_letters(reduced_alphabet_t& red, 1408 const_twa_graph_ptr& mmw, 1409 const unsigned n_env) 1410 { 1411 //To avoid recalc 1412 std::set<int> all_bdd; 1413 std::set<int> treated_bdd; 1414 std::unordered_multimap<size_t, std::pair<unsigned, std::set<int>>> 1415 sigma_map; 1416 1417 const unsigned n_groups = red.n_groups; 1418 for (unsigned groupidx = 0; groupidx < n_groups; ++groupidx) 1419 { 1420 all_bdd.clear(); 1421 // List all bdds occuring in this group, no matter the order 1422 for (unsigned s = 0; s < n_env; ++s) 1423 { 1424 if (red.which_group[s] != groupidx) 1425 continue; 1426 for (const auto& e : mmw->out(s)) 1427 all_bdd.insert(e.cond.id()); 1428 } 1429 // Check if we have already decomposed them 1430 const size_t sigma_hash = id_cont_hasher()(all_bdd); 1431 { 1432 auto eq_range = sigma_map.equal_range(sigma_hash); 1433 bool treated = false; 1434 for (auto it = eq_range.first; it != eq_range.second; ++it) 1435 { 1436 if (all_bdd == it->second.second) 1437 { 1438 red.all_letters. 1439 emplace_back(red.all_letters[it->second.first]); 1440 red.share_sigma_with.push_back(it->second.first); 1441 trace << "Group " << groupidx << " shares an alphabet with " 1442 << it->second.first << '\n'; 1443 treated = true; 1444 break; 1445 } 1446 } 1447 if (treated) 1448 continue; 1449 else 1450 { 1451 // Insert it already into the sigma_map 1452 trace << "Group " << groupidx << " generates a new alphabet\n"; 1453 sigma_map.emplace(std::piecewise_construct, 1454 std::forward_as_tuple(sigma_hash), 1455 std::forward_as_tuple(groupidx, 1456 std::move(all_bdd))); 1457 } 1458 } 1459 1460 red.share_sigma_with.push_back(groupidx); 1461 red.all_letters.emplace_back(); 1462 auto& group_letters = red.all_letters.back(); 1463 1464 treated_bdd.clear(); 1465 1466 for (unsigned s = 0; s < n_env; ++s) 1467 { 1468 if (red.which_group[s] != groupidx) 1469 continue; 1470 for (const auto& e : mmw->out(s)) 1471 { 1472 bdd rcond = e.cond; 1473 const int econd_id = rcond.id(); 1474 trace << rcond << " - " << econd_id << std::endl; 1475 if (treated_bdd.count(econd_id)) 1476 { 1477 trace << "Already treated" << std::endl; 1478 continue; 1479 } 1480 treated_bdd.insert(econd_id); 1481 1482 assert(rcond != bddfalse && "Deactivated edges are forbiden"); 1483 // Check against all currently used "letters" 1484 const size_t osize = group_letters.size(); 1485 for (size_t i = 0; i < osize; ++i) 1486 { 1487 if (group_letters[i].first == rcond) 1488 { 1489 rcond = bddfalse; 1490 group_letters[i].second.insert(econd_id); 1491 break; 1492 } 1493 bdd inter = group_letters[i].first & rcond; 1494 if (inter == bddfalse) 1495 continue; // No intersection 1496 if (group_letters[i].first == inter) 1497 group_letters[i].second.insert(econd_id); 1498 else 1499 { 1500 group_letters[i].first -= inter; 1501 group_letters.emplace_back(inter, 1502 group_letters[i].second); 1503 group_letters.back().second.insert(econd_id); 1504 } 1505 1506 rcond -= inter; 1507 // Early exit? 1508 if (rcond == bddfalse) 1509 break; 1510 } 1511 // Leftovers? 1512 if (rcond != bddfalse) 1513 group_letters.emplace_back(rcond, std::set<int>{econd_id}); 1514 } 1515 } 1516 #ifdef TRACE 1517 trace << "this group letters" << std::endl; 1518 auto sp = [&](const auto& c) 1519 {std::for_each(c.begin(), c.end(), 1520 [&](auto& e){trace << e << ' '; }); }; 1521 for (const auto& p : group_letters) 1522 { 1523 trace << p.first << " - "; 1524 sp(p.second); 1525 trace << std::endl; 1526 } 1527 #endif 1528 } 1529 } 1530 1531 // compute bisimilar minimal letters 1532 // We say two letters are bisimilar if they have the same destination 1533 // for all src states compute_bisim_letter(reduced_alphabet_t & red,const_twa_graph_ptr & mmw,const unsigned n_env,const unsigned i)1534 void compute_bisim_letter(reduced_alphabet_t& red, 1535 const_twa_graph_ptr& mmw, 1536 const unsigned n_env, 1537 const unsigned i) 1538 1539 { 1540 // Do not use -1u to mark no succ, as this is "bad" for the 1541 // hashing function -> Use first unused state 1542 const unsigned no_succ_mark = mmw->num_states(); 1543 const auto& mlv = red.minimal_letters_vec.at(i); 1544 const unsigned n_ml = mlv.size(); 1545 const unsigned nsg = std::count(red.which_group.begin(), 1546 red.which_group.end(), i); 1547 assert(nsg != 0 && nsg <= n_env); 1548 1549 std::vector<unsigned> dest_vec(nsg); 1550 1551 // hashed id -> <dest vector, list of sim indices vec> 1552 std::unordered_multimap<size_t, 1553 std::pair<std::vector<unsigned>, std::vector<unsigned>>> sim_map; 1554 1555 auto get_e_dst = [&](const auto& e_env)->unsigned 1556 { 1557 return mmw->out(e_env.dst).begin()->dst; 1558 }; 1559 1560 for (unsigned idx = 0; idx < n_ml; ++idx) 1561 { 1562 const bdd& ml = mlv[idx]; 1563 const std::set<int>& ml_impl = red.minimal_letters[i][ml].first; 1564 1565 dest_vec.clear(); 1566 for (unsigned s = 0; s < n_env; ++s) 1567 { 1568 if (red.which_group[s] != i) 1569 continue; 1570 // Check which outgoing edge is implied by ml 1571 // Note there can be only one due to input determinism 1572 // Note if there is no such edge we mark it 1573 unsigned this_dst = no_succ_mark; 1574 for (const auto& e : mmw->out(s)) 1575 if (ml_impl.count(e.cond.id())) 1576 { 1577 this_dst = get_e_dst(e); 1578 break; 1579 } 1580 dest_vec.push_back(this_dst); 1581 } 1582 assert(dest_vec.size() == nsg); 1583 1584 // We constructed the dst vector, check if it already exists 1585 size_t id = id_cont_hasher()(dest_vec); 1586 auto [eq, eq_end] = sim_map.equal_range(id); 1587 bool is_sim = false; 1588 for (; eq != eq_end; ++eq) 1589 if (dest_vec == eq->second.first) 1590 { 1591 eq->second.second.push_back(idx); 1592 is_sim = true; 1593 break; 1594 } 1595 if (!is_sim) 1596 sim_map.emplace(id, 1597 std::make_pair(dest_vec, 1598 std::vector<unsigned>{idx})); 1599 } 1600 // save results 1601 red.bisim_letters.emplace_back(); 1602 auto& bs = red.bisim_letters.back(); 1603 // We need to sort the results because the 1604 // construction of the sat-problem latter on depends on it 1605 for (auto&& [id, pv] : sim_map) 1606 { 1607 // We want front (the representative) to be the smallest 1608 std::sort(pv.second.begin(), pv.second.end()); 1609 bs.emplace_back(std::move(pv.second)); 1610 } 1611 // Sort the bisimilar classes as well for the same reason 1612 std::sort(bs.begin(), bs.end(), 1613 [](const auto& v1, const auto& v2) 1614 {return v1.front() < v2.front(); }); 1615 //Done 1616 } 1617 1618 // If two letters take the same original edge / go to the same destination 1619 // for all states, then one can represent the other 1620 // Here we search a minimal subset of letters that can represent 1621 // all the others compute_minimal_letters(reduced_alphabet_t & red,const_twa_graph_ptr & mmw,const unsigned n_env)1622 void compute_minimal_letters(reduced_alphabet_t& red, 1623 const_twa_graph_ptr& mmw, 1624 const unsigned n_env) 1625 { 1626 // mmw is deterministic with respect to inputs 1627 // So if two letters imply the same conditions 1628 // they take the same edges and can therefore be represented 1629 // by just one of them 1630 1631 std::unordered_multimap<size_t, bdd> tgt_map; 1632 1633 const unsigned n_groups = red.n_groups; 1634 red.minimal_letters.clear(); 1635 red.minimal_letters.reserve(n_groups); 1636 red.n_red_sigma = 0; 1637 1638 for (unsigned i = 0; i < n_groups; ++i) 1639 { 1640 // If a group shares an alphabet with another group, 1641 // then they also share the minimal letters 1642 // Again, copied to avoid overhead 1643 if (red.share_sigma_with[i] != i) 1644 { 1645 assert(red.share_sigma_with[i] < i); 1646 red.minimal_letters 1647 .push_back(red.minimal_letters[red.share_sigma_with[i]]); 1648 red.minimal_letters_vec 1649 .push_back(red.minimal_letters_vec[red.share_sigma_with[i]]); 1650 continue; 1651 } 1652 1653 tgt_map.clear(); 1654 1655 red.minimal_letters.emplace_back(); 1656 auto& group_min_letters = red.minimal_letters.back(); 1657 1658 // Check all letters 1659 for (const auto& [letter, impl_cond] : red.all_letters[i]) 1660 { 1661 // Check if this set exists 1662 size_t hv = id_cont_hasher()(impl_cond); 1663 auto eq_r = tgt_map.equal_range(hv); 1664 bool covered = false; 1665 for (auto min_letter_it = eq_r.first; min_letter_it != eq_r.second; 1666 ++min_letter_it) 1667 { 1668 auto& min_letter_struct = 1669 group_min_letters.at(min_letter_it->second); 1670 // Check if truly compatible 1671 if (impl_cond == min_letter_struct.first) 1672 { 1673 // letter can be represented by min_letter 1674 min_letter_struct.second.insert(letter.id()); 1675 covered = true; 1676 break; 1677 } 1678 } 1679 if (!covered) 1680 { 1681 // We have found a new minimal letter 1682 // Update tgt_map and minimal_letters 1683 tgt_map.emplace(hv, letter); 1684 group_min_letters.emplace(letter, 1685 std::make_pair(impl_cond, 1686 std::set<int>{letter.id()})); 1687 } 1688 } 1689 red.minimal_letters_vec.emplace_back(); 1690 auto& gmlv = red.minimal_letters_vec.back(); 1691 gmlv.reserve(red.minimal_letters.back().size()); 1692 const auto& mlg = red.minimal_letters.back(); 1693 trace << "Group min letters\n"; 1694 for (const auto& mlit : mlg) 1695 { 1696 trace << mlit.first << '\n'; 1697 gmlv.push_back(mlit.first); 1698 } 1699 // Sort it 1700 // todo: stable sort? 1701 std::sort(gmlv.begin(), gmlv.end(), 1702 [](const bdd& l, const bdd& r) 1703 {return l.id() < r.id(); }); 1704 } 1705 1706 1707 for (unsigned i = 0; i < n_groups; i++) 1708 { 1709 // Compute the bisimilar minimal letters 1710 compute_bisim_letter(red, mmw, n_env, i); 1711 1712 red.n_red_sigma = std::max(red.n_red_sigma, 1713 (unsigned) red.bisim_letters.back().size()); 1714 } 1715 1716 // Save if groups share not only the alphabet, 1717 // but also which letters are bisimilar 1718 red.share_bisim_with = std::vector<unsigned>(n_groups, -1u); 1719 for (unsigned i = 0; i < n_groups; i++) 1720 { 1721 if (red.share_sigma_with[i] == i) 1722 red.share_bisim_with[i] = i; // Its own class 1723 for (unsigned j = 0; j < i; ++j) 1724 if (red.share_sigma_with[j] == red.share_sigma_with[i] 1725 && red.bisim_letters[j] == red.bisim_letters[i]) 1726 { 1727 red.share_bisim_with[i] = j; 1728 break; 1729 } 1730 if (red.share_bisim_with[i] == -1u) 1731 red.share_bisim_with[i] = i; 1732 } 1733 trace << "All min letters " << red.n_red_sigma << '\n'; 1734 } 1735 1736 // We construct a new graph with edges labeled by the minimal letters 1737 // and only holding the env states split_on_minimal(const reduced_alphabet_t & red,const_twa_graph_ptr mmw,const unsigned n_env)1738 twa_graph_ptr split_on_minimal(const reduced_alphabet_t& red, 1739 const_twa_graph_ptr mmw, 1740 const unsigned n_env) 1741 { 1742 const unsigned n_groups = red.n_groups; 1743 auto split_mmw = make_twa_graph(mmw->get_dict()); 1744 split_mmw->copy_ap_of(mmw); 1745 split_mmw->new_states(n_env); 1746 1747 // We only need env states 1748 auto get_e_dst = [&](const auto& e_env) 1749 { 1750 return mmw->out(e_env.dst).begin()->dst; 1751 }; 1752 1753 // We only need the transitions implied 1754 // by minimal and representative letters 1755 // Build a map from bdd-ids in the graph 1756 // to the set of implied minimal letters 1757 // Note we can do this group by group 1758 std::vector<std::unordered_map<int, std::set<int>>> 1759 l_map_glob(red.n_groups, 1760 std::unordered_map<int, std::set<int>>{}); 1761 1762 // todo Check if this is bottleneck 1763 // Note: if two groups share the alphabet AND the 1764 // which letters are bisimilar -> They also share the map 1765 for (unsigned i = 0; i < n_groups; ++i) 1766 { 1767 auto& l_map = l_map_glob.at(red.share_bisim_with[i]); 1768 if (l_map.empty()) 1769 { 1770 assert(red.share_bisim_with[i] == i); 1771 const auto& bisim_idx_vec = red.bisim_letters[i]; 1772 for (const auto& a_bisim : bisim_idx_vec) 1773 { 1774 assert(a_bisim.front() < red.minimal_letters_vec[i].size()); 1775 const bdd& repr_bdd = 1776 red.minimal_letters_vec[i].at(a_bisim.front()); 1777 const auto& it_mlb = 1778 red.minimal_letters[i].at(repr_bdd); 1779 const int this_id = repr_bdd.id(); 1780 for (int implied_by : it_mlb.first) 1781 l_map[implied_by].insert(this_id); 1782 } 1783 } 1784 else 1785 assert(red.share_bisim_with[i] < i); 1786 1787 const auto lmap_end = l_map.end(); 1788 for (unsigned s = 0; s < n_env; ++s) 1789 { 1790 if (red.which_group[s] != i) 1791 continue; 1792 for (const auto &e : mmw->out(s)) 1793 { 1794 // Edge might be simulated by another 1795 auto it_e = l_map.find(e.cond.id()); 1796 if (it_e != lmap_end) 1797 { 1798 const auto& ml_l = it_e->second; 1799 unsigned dst_e = get_e_dst(e); 1800 for (int bdd_id : ml_l) 1801 split_mmw->new_edge(s, dst_e, bdd_from_int(bdd_id)); 1802 } 1803 else 1804 trace << e.src << " - " << e.cond.id() << " > " << e.dst 1805 << " is simulated\n"; 1806 } 1807 } 1808 } 1809 1810 // todo sort edges inplace? bdd_less_than vs bdd_less_than_stable 1811 split_mmw-> 1812 get_graph().sort_edges_([](const auto& e1, const auto& e2) 1813 { 1814 return std::make_pair(e1.src, 1815 e1.cond.id()) 1816 < std::make_pair(e2.src, 1817 e2.cond.id()); 1818 }); 1819 split_mmw->get_graph().chain_edges_(); 1820 #ifdef TRACE 1821 trace << "Orig split aut\n"; 1822 print_hoa(std::cerr, mmw) << '\n'; 1823 { 1824 auto ss = make_twa_graph(split_mmw, twa::prop_set::all()); 1825 for (unsigned group = 0; group < red.n_groups; ++group) 1826 { 1827 std::vector<bdd> edge_num; 1828 for (unsigned i = 0; i < red.minimal_letters_vec[group].size(); ++i) 1829 { 1830 edge_num.push_back( 1831 bdd_ithvar(ss->register_ap("g"+std::to_string(group) 1832 +"e"+std::to_string(i)))); 1833 } 1834 for (unsigned s = 0; s < n_env; ++s) 1835 { 1836 if (red.which_group.at(s) != group) 1837 continue; 1838 for (auto& e : ss->out(s)) 1839 e.cond = 1840 edge_num.at( 1841 find_first_index_of(red.bisim_letters[group], 1842 [&, cc = e.cond](const auto& bs_idx_vec) 1843 {return cc 1844 == red.minimal_letters_vec[group] 1845 [bs_idx_vec.front()]; })); 1846 } 1847 } 1848 trace << "Relabeled split aut\n"; 1849 print_hoa(std::cerr, ss) << '\n'; 1850 trace << "Bisim ids\n"; 1851 for (unsigned i = 0; i < n_groups; ++i) 1852 { 1853 trace << "group " << i << '\n'; 1854 for (const auto& idx_vec : red.bisim_letters[i]) 1855 trace << red.minimal_letters_vec[i][idx_vec.front()].id() << '\n'; 1856 trace << "ids in the edge of the group\n"; 1857 for (unsigned s = 0; s < n_env; ++s) 1858 if (red.which_group.at(s) == i) 1859 for (const auto& e : split_mmw->out(s)) 1860 trace << e.src << "->" << e.dst << ':' << e.cond.id() << '\n'; 1861 } 1862 } 1863 #endif 1864 return split_mmw; 1865 } 1866 1867 std::pair<twa_graph_ptr, reduced_alphabet_t> reduce_and_split(const_twa_graph_ptr mmw,const unsigned n_env,const square_matrix<bool,true> & incompmat,stopwatch & sw)1868 reduce_and_split(const_twa_graph_ptr mmw, const unsigned n_env, 1869 const square_matrix<bool, true>& incompmat, 1870 stopwatch& sw) 1871 { 1872 reduced_alphabet_t red; 1873 std::tie(red.n_groups, red.which_group) = trans_comp_classes(incompmat); 1874 dotimeprint << "Done trans comp " << red.n_groups 1875 << " - " << sw.stop() << '\n'; 1876 1877 compute_all_letters(red, mmw, n_env); 1878 dotimeprint << "Done comp all letters " << " - " << sw.stop() << '\n'; 1879 1880 compute_minimal_letters(red, mmw, n_env); 1881 #ifdef MINTIMINGS 1882 dotimeprint << "Done comp all min sim letters "; 1883 for (const auto& al : red.bisim_letters) 1884 dotimeprint << al.size() << ' '; 1885 dotimeprint << " - " << sw.stop() << '\n'; 1886 #endif 1887 1888 twa_graph_ptr split_mmw = split_on_minimal(red, mmw, n_env); 1889 dotimeprint << "Done splitting " << sw.stop() << '\n'; 1890 trace << std::endl; 1891 1892 return std::make_pair(split_mmw, red); 1893 } 1894 1895 // Things for lit mapping 1896 // mapping (states, classes) 1897 struct xi_t : public std::pair<unsigned, unsigned> 1898 { 1899 unsigned& x; 1900 unsigned& i; 1901 xi_t__anonff402b370711::xi_t1902 constexpr xi_t(unsigned x_in, unsigned i_in) 1903 : std::pair<unsigned, unsigned>{x_in, i_in} 1904 , x{this->first} 1905 , i{this->second} 1906 { 1907 } 1908 xi_t__anonff402b370711::xi_t1909 constexpr xi_t(const xi_t& xi) 1910 : xi_t{xi.x, xi.i} 1911 { 1912 } 1913 operator =__anonff402b370711::xi_t1914 xi_t& operator=(const xi_t& xi) 1915 { 1916 x = xi.x; 1917 i = xi.i; 1918 return *this; 1919 } 1920 xi_t__anonff402b370711::xi_t1921 xi_t(xi_t&& xi) 1922 : xi_t{xi.x, xi.i} 1923 { 1924 } 1925 }; 1926 1927 // mapping (classes, letters, classes) 1928 struct iaj_t 1929 { hash__anonff402b370711::iaj_t1930 size_t hash() const noexcept 1931 { 1932 size_t h = i; 1933 h <<= 21; 1934 h += a; 1935 h <<= 20; 1936 h += j; 1937 return std::hash<size_t>()(h); 1938 } operator ==__anonff402b370711::iaj_t1939 bool operator==(const iaj_t& rhs) const 1940 { 1941 return std::tie(i, a, j) == std::tie(rhs.i, rhs.a, rhs.j); 1942 } operator <__anonff402b370711::iaj_t1943 bool operator<(const iaj_t& rhs) const 1944 { 1945 return std::tie(i, a, j) < std::tie(rhs.i, rhs.a, rhs.j); 1946 } 1947 1948 unsigned i, a, j; 1949 }; 1950 1951 auto iaj_hash = __anonff402b371902(const iaj_t& iaj) 1952 [](const iaj_t& iaj) noexcept {return iaj.hash(); }; 1953 auto iaj_eq = __anonff402b371a02(const iaj_t& l, const iaj_t& r)1954 [](const iaj_t& l, const iaj_t& r){return l == r; }; __anonff402b371b02(const iaj_t& l, const iaj_t& r)1955 auto iaj_less = [](const iaj_t& l, const iaj_t& r){return l < r; }; 1956 1957 template<bool USE_PICO> 1958 struct lit_mapper; 1959 1960 template<> 1961 struct lit_mapper<true> 1962 { 1963 // x and y in same class? 1964 //x <-> x, i <-> y 1965 using xy_t = xi_t; 1966 // using k-th product of out-cond of state x for minimal letter u 1967 // u <-> i, x <-> a, k <-> k 1968 using uxk_t = iaj_t; 1969 1970 PicoSAT* psat_; 1971 unsigned n_classes_; 1972 const unsigned n_env_, n_sigma_red_; 1973 int next_var_; 1974 bool frozen_xi_, frozen_iaj_, frozen_si_; 1975 //xi -> lit 1976 std::unordered_map<xi_t, int, pair_hash> sxi_map_; 1977 //xy -> lit 1978 std::unordered_map<xi_t, int, pair_hash> ixy_map_; 1979 //iaj -> lit 1980 std::unordered_map<iaj_t, int, 1981 decltype(iaj_hash), 1982 decltype(iaj_eq)> ziaj_map_{1, iaj_hash, iaj_eq}; 1983 //iaj -> lit 1984 std::unordered_map<uxk_t, int, 1985 decltype(iaj_hash), 1986 decltype(iaj_eq)> cuxk_map_{1, iaj_hash, iaj_eq}; 1987 // all lits 1988 std::vector<int> all_lits; 1989 lit_mapper__anonff402b370711::lit_mapper1990 lit_mapper(unsigned n_classes, unsigned n_env, 1991 unsigned n_sigma_red) 1992 : psat_{picosat_init()} 1993 , n_classes_{n_classes} 1994 , n_env_{n_env} 1995 , n_sigma_red_{n_sigma_red} 1996 , next_var_{std::numeric_limits<int>::min()} 1997 , frozen_xi_{false} 1998 , frozen_iaj_{false} 1999 { 2000 next_var_ = get_var_(); 2001 // There are at most n_classes*n_env literals in the sxi_map 2002 // Usually they all appear 2003 sxi_map_.reserve(n_classes_*n_env_); 2004 // There are at most n_classes*n_classes*n_sigma_red in ziaj_map 2005 // However they are usually more scarce 2006 ziaj_map_.reserve((n_classes_*n_classes_*n_sigma_red_)/3); 2007 } 2008 ~lit_mapper__anonff402b370711::lit_mapper2009 ~lit_mapper() 2010 { 2011 picosat_reset(psat_); 2012 } 2013 get_var___anonff402b370711::lit_mapper2014 int get_var_() 2015 { 2016 return picosat_inc_max_var(psat_); 2017 } 2018 inc_var__anonff402b370711::lit_mapper2019 void inc_var() 2020 { 2021 all_lits.push_back(next_var_); 2022 next_var_ = get_var_(); 2023 } 2024 sxi2lit__anonff402b370711::lit_mapper2025 int sxi2lit(xi_t xi) 2026 { 2027 assert(xi.x < n_env_ && "Exceeds max state number."); 2028 assert(xi.i < n_classes_ && "Exceeds max source class."); 2029 auto [it, inserted] = sxi_map_.try_emplace(xi, next_var_); 2030 if (inserted) 2031 inc_var(); 2032 assert((!frozen_xi_ || !inserted) && "Created lit when frozen."); 2033 return it->second; 2034 } 2035 sxi2lit__anonff402b370711::lit_mapper2036 int sxi2lit(xi_t xi) const 2037 { 2038 assert(sxi_map_.count(xi) && "Cannot create lit when const."); 2039 return sxi_map_.at(xi); 2040 } 2041 get_sxi__anonff402b370711::lit_mapper2042 int get_sxi(xi_t xi) const // Gets the literal or zero of not defined 2043 { 2044 auto it = sxi_map_.find(xi); 2045 if (it == sxi_map_.end()) 2046 return 0; 2047 else 2048 return it->second; 2049 } 2050 freeze_xi__anonff402b370711::lit_mapper2051 void freeze_xi() 2052 { 2053 frozen_xi_ = true; 2054 } unfreeze_xi__anonff402b370711::lit_mapper2055 void unfreeze_xi() 2056 { 2057 frozen_xi_ = false; 2058 } 2059 ziaj2lit__anonff402b370711::lit_mapper2060 int ziaj2lit(iaj_t iaj) 2061 { 2062 assert(iaj.i < n_classes_ && "Exceeds source class."); 2063 assert(iaj.a < n_sigma_red_ && "Exceeds max letter idx."); 2064 assert(iaj.j < n_classes_&& "Exceeds dest class."); 2065 auto [it, inserted] = ziaj_map_.try_emplace(iaj, next_var_); 2066 assert((!frozen_iaj_ || !inserted) && "Created lit when frozen."); 2067 if (inserted) 2068 inc_var(); 2069 return it->second; 2070 } 2071 ziaj2lit__anonff402b370711::lit_mapper2072 int ziaj2lit(iaj_t iaj) const 2073 { 2074 assert(ziaj_map_.count(iaj) && "Cannot create lit when const."); 2075 return ziaj_map_.at(iaj); 2076 } get_iaj__anonff402b370711::lit_mapper2077 int get_iaj(iaj_t iai) const // Gets the literal or zero of not defined 2078 { 2079 auto it = ziaj_map_.find(iai); 2080 if (it == ziaj_map_.end()) 2081 return 0; 2082 else 2083 return it->second; 2084 } 2085 freeze_iaj__anonff402b370711::lit_mapper2086 void freeze_iaj() 2087 { 2088 frozen_iaj_ = true; 2089 } unfreeze_iaj__anonff402b370711::lit_mapper2090 void unfreeze_iaj() 2091 { 2092 frozen_iaj_ = false; 2093 } 2094 ixy2lit__anonff402b370711::lit_mapper2095 int ixy2lit(xy_t xy) 2096 { 2097 assert(xy.x < n_env_ && "Exceeds max state number."); 2098 assert(xy.i < n_env_ && "Exceeds max state number."); 2099 auto [it, inserted] = ixy_map_.try_emplace(xy, next_var_); 2100 if (inserted) 2101 inc_var(); 2102 return it->second; 2103 } 2104 ixy2lit__anonff402b370711::lit_mapper2105 int ixy2lit(xy_t xy) const 2106 { 2107 return ixy_map_.at(xy); 2108 } 2109 cuxk2lit__anonff402b370711::lit_mapper2110 int cuxk2lit(uxk_t uxk) 2111 { 2112 assert(uxk.a < n_env_ && "Exceeds max state number."); 2113 auto [it, inserted] = cuxk_map_.try_emplace(uxk, next_var_); 2114 if (inserted) 2115 inc_var(); 2116 return it->second; 2117 } 2118 cuxk2lit__anonff402b370711::lit_mapper2119 int cuxk2lit(uxk_t uxk) const 2120 { 2121 return cuxk_map_.at(uxk); 2122 } 2123 print__anonff402b370711::lit_mapper2124 std::ostream& print(std::ostream& os = std::cout, 2125 std::vector<int>* sol = nullptr) 2126 { 2127 bool hs = sol != nullptr; 2128 auto ts = [&](int i){return std::to_string(i); }; 2129 2130 { 2131 std::map<xi_t, int> xi_tmp(sxi_map_.begin(), 2132 sxi_map_.end()); 2133 os << "x - i -> lit" << (hs ? " - sol\n" : "\n"); 2134 for (auto& it : xi_tmp) 2135 os << it.first.x << " - " << it.first.i << " -> " << it.second 2136 << (hs ? " - " + ts(sol->at(sxi_map_.at(it.first))) : " ") 2137 << '\n'; 2138 } 2139 { 2140 std::map<iaj_t, int, decltype(iaj_less)> 2141 iaj_tmp(ziaj_map_.begin(), ziaj_map_.end(), iaj_less); 2142 os << "i - a - j -> lit\n"; 2143 for (auto& it : iaj_tmp) 2144 os << it.first.i << " - " << it.first.a << " - " << it.first.j 2145 << " -> " << it.second 2146 << (hs ? " - " + ts(sol->at(ziaj_map_.at(it.first))) : " ") 2147 << '\n'; 2148 } 2149 { 2150 std::map<xy_t, int> xy_tmp(ixy_map_.begin(), 2151 ixy_map_.end()); 2152 os << "x - y -> lit" << (hs ? " - sol\n" : "\n"); 2153 for (auto& it : xy_tmp) 2154 os << it.first.x << " - " << it.first.i << " -> " << it.second 2155 << (hs ? " - " + ts(sol->at(ixy_map_.at(it.first))) : " ") 2156 << '\n'; 2157 } 2158 { 2159 std::map<uxk_t, int, decltype(iaj_less)> 2160 uxk_tmp(cuxk_map_.begin(), cuxk_map_.end(), iaj_less); 2161 os << "u - x - k -> lit\n"; 2162 for (auto& it : uxk_tmp) 2163 os << it.first.i << " - " << it.first.a << " - " << it.first.j 2164 << " -> " << it.second 2165 << (hs ? " - " + ts(sol->at(cuxk_map_.at(it.first))) : " ") 2166 << '\n'; 2167 } 2168 return os; 2169 } 2170 }; 2171 2172 using ia_t = xi_t; 2173 2174 2175 using pso_pair = std::pair<unsigned, bdd>; 2176 struct pso_order 2177 { operator ()__anonff402b370711::pso_order2178 bool operator()(const pso_pair& p1, 2179 const pso_pair& p2) const noexcept 2180 { 2181 return p1.first < p2.first; 2182 } 2183 }; 2184 2185 template<bool USE_PICO> 2186 struct mm_sat_prob_t; 2187 2188 template<> 2189 struct mm_sat_prob_t<true> 2190 { mm_sat_prob_t__anonff402b370711::mm_sat_prob_t2191 mm_sat_prob_t(unsigned n_classes, unsigned n_env, 2192 unsigned n_sigma_red) 2193 : lm(n_classes, n_env, n_sigma_red) 2194 , n_classes{lm.n_classes_} 2195 { 2196 state_cover_clauses.reserve(n_classes); 2197 trans_cover_clauses.reserve(n_classes*n_sigma_red); 2198 } 2199 add_static__anonff402b370711::mm_sat_prob_t2200 void add_static(int lit) 2201 { 2202 picosat_add(lm.psat_, lit); 2203 } 2204 template<class CONT> add_static__anonff402b370711::mm_sat_prob_t2205 void add_static(CONT& lit_cont) 2206 { 2207 for (int lit : lit_cont) 2208 picosat_add(lm.psat_, lit); 2209 } 2210 2211 set_variable_clauses__anonff402b370711::mm_sat_prob_t2212 void set_variable_clauses() 2213 { 2214 trace << "c Number of local clauses " 2215 << state_cover_clauses.size() + trans_cover_clauses.size() << '\n'; 2216 trace << "c Cover clauses\n"; 2217 picosat_push(lm.psat_); 2218 for (auto& [_, clause] : state_cover_clauses) 2219 { 2220 // Clause is not nullterminated! 2221 clause.push_back(0); 2222 picosat_add_lits(lm.psat_, clause.data()); 2223 trace_clause(clause); 2224 clause.pop_back(); 2225 } 2226 trace << "c Transition cover clauses\n"; 2227 for (auto& elem : trans_cover_clauses) 2228 { 2229 // Clause is not nullterminated! 2230 auto& clause = elem.second; 2231 clause.push_back(0); 2232 picosat_add_lits(lm.psat_, clause.data()); 2233 trace_clause(clause); 2234 clause.pop_back(); 2235 } 2236 } 2237 2238 std::vector<int> get_sol__anonff402b370711::mm_sat_prob_t2239 get_sol() 2240 { 2241 // Returns a vector of assignments 2242 // The vector is empty iff the prob is unsat 2243 // res[i] == -1 : i not used in lit mapper 2244 // res[i] == 0 : i is assigned false 2245 // res[i] == 1 : i is assigned true 2246 switch (picosat_sat(lm.psat_, -1)) 2247 { 2248 case PICOSAT_UNSATISFIABLE: 2249 return {}; 2250 case PICOSAT_SATISFIABLE: 2251 { 2252 std::vector<int> 2253 res(1 + (unsigned) picosat_variables(lm.psat_), -1); 2254 SPOT_ASSUME(res.data()); // g++ 11 believes data might be nullptr 2255 res[0] = 0; // Convention 2256 for (int lit : lm.all_lits) 2257 res[lit] = picosat_deref(lm.psat_, lit); 2258 #ifdef TRACE 2259 trace << "Sol is\n"; 2260 for (unsigned i = 0; i < res.size(); ++i) 2261 trace << i << ": " << res[i] << '\n'; 2262 #endif 2263 return res; 2264 } 2265 default: 2266 throw std::runtime_error("Unknown error in picosat."); 2267 } 2268 } 2269 unset_variable_clauses__anonff402b370711::mm_sat_prob_t2270 void unset_variable_clauses() 2271 { 2272 picosat_pop(lm.psat_); 2273 } 2274 n_lits__anonff402b370711::mm_sat_prob_t2275 unsigned n_lits() const 2276 { 2277 return lm.next_var_ - 1; 2278 } 2279 n_clauses__anonff402b370711::mm_sat_prob_t2280 unsigned n_clauses() const 2281 { 2282 return (unsigned) picosat_added_original_clauses(lm.psat_); 2283 } 2284 2285 // The mapper 2286 lit_mapper<true> lm; 2287 2288 // The current number of classes 2289 unsigned& n_classes; 2290 2291 // partial solution, incompatibility 2292 // Clauses have to be added, but existing ones 2293 // remain unchanged 2294 2295 // Add the new lit each time n_classes is increased 2296 std::vector<std::pair<unsigned, std::vector<int>>> state_cover_clauses; 2297 std::unordered_map<ia_t, std::vector<int>, pair_hash> trans_cover_clauses; 2298 2299 // A vector of maps group -> minimal letter -> set of pairs(state, ocond) 2300 // The set is only ordered with respect to the state 2301 using pso_set = std::set<pso_pair, pso_order>; 2302 std::vector<std::vector<pso_set>> ocond_maps; 2303 // A matrix tracking if two states 2304 // are already "tracked" for extended incompatibility 2305 square_matrix<bool, true> tracked_s_pair; 2306 // A map relating a bdd to a list of its cubes using its 2307 // id as key 2308 std::unordered_map<int, std::vector<bdd>> cube_map; 2309 // A map that indicates if two cubes are compatible or not via their id 2310 std::unordered_map<std::pair<int, int>, bool, pair_hash> cube_incomp_map; 2311 }; 2312 2313 template<> add_static(std::vector<int> & lit_cont)2314 void mm_sat_prob_t<true>::add_static(std::vector<int>& lit_cont) 2315 { 2316 picosat_add_lits(lm.psat_, lit_cont.data()); 2317 } 2318 2319 template <bool USE_PICO> 2320 void add_trans_cstr_f(mm_sat_prob_t<USE_PICO>&, 2321 const square_matrix<bool, true>&, 2322 const iaj_t, const unsigned, const int, 2323 const unsigned, 2324 const std::vector<unsigned>&, 2325 const std::vector<unsigned>&); 2326 2327 // Add the constraints on transitions if the src class and possibly 2328 // the dst class is a partial solution 2329 template <> 2330 void add_trans_cstr_f(mm_sat_prob_t<true> & mm_pb,const square_matrix<bool,true> & incompmat,const iaj_t iaj,const unsigned fdj,const int iajlit,const unsigned fdx_idx,const std::vector<unsigned> & group_states_,const std::vector<unsigned> & has_a_edge_)2331 add_trans_cstr_f<true>(mm_sat_prob_t<true>& mm_pb, 2332 const square_matrix<bool, true>& incompmat, 2333 const iaj_t iaj, const unsigned fdj, const int iajlit, 2334 const unsigned fdx_idx, 2335 const std::vector<unsigned>& group_states_, 2336 const std::vector<unsigned>& has_a_edge_) 2337 { 2338 const auto& lm = mm_pb.lm; 2339 const unsigned& n_sg = group_states_.size(); 2340 const unsigned fdx = group_states_[fdx_idx]; 2341 const unsigned fdx_succ = has_a_edge_[fdx_idx]; 2342 assert(fdj < incompmat.dim()); 2343 2344 static std::vector<int> clause(4, 0); 2345 for (unsigned xidx = 0; xidx < n_sg; ++xidx) 2346 { 2347 if (fdj == fdx_succ && xidx == fdx_idx) 2348 continue; // founding state source -> founding state dst 2349 2350 const unsigned x = group_states_[xidx]; 2351 // x incompatible with founding state 2352 // (Only here due to transitive closure) 2353 // -> Nothing to do, taken care on in incomp section 2354 if (incompmat.get(fdx, x)) 2355 continue; 2356 // Successor 2357 const unsigned xprime = has_a_edge_[xidx]; 2358 // -1u -> No edge, always ok 2359 // xprime == fdj -> Edge to founding state, always ok 2360 if (xprime == -1u || xprime == fdj) 2361 continue; 2362 2363 auto clause_it = clause.begin(); 2364 *clause_it = -iajlit; 2365 // If xprime and the dest class are incompatible 2366 // -> source state can not be in i if iajlit is active 2367 if (xidx != fdx_idx) 2368 // Must be in src_class as it is founding 2369 *(++clause_it) = -lm.sxi2lit({x, iaj.i}); 2370 // No need to add xprime if it is not compatible 2371 // with the successor of the founding state of src (if existent) 2372 // or the dst class 2373 if ((fdx_succ == -1u || !incompmat.get(fdx_succ, xprime)) 2374 && !incompmat.get(fdj, xprime)) 2375 *(++clause_it) = lm.sxi2lit({xprime, iaj.j}); 2376 2377 *(++clause_it) = 0; 2378 mm_pb.add_static(clause); 2379 trace_clause(clause); 2380 } 2381 } 2382 2383 template <bool USE_PICO> 2384 mm_sat_prob_t<USE_PICO> build_init_prob(const_twa_graph_ptr split_mmw,const square_matrix<bool,true> & incompmat,const reduced_alphabet_t & red,const part_sol_t & psol,const unsigned n_env)2385 build_init_prob(const_twa_graph_ptr split_mmw, 2386 const square_matrix<bool, true>& incompmat, 2387 const reduced_alphabet_t& red, 2388 const part_sol_t& psol, 2389 const unsigned n_env) 2390 { 2391 const auto& psolv = psol.psol; 2392 const unsigned n_classes = psolv.size(); 2393 const unsigned n_red = red.n_red_sigma; 2394 const unsigned n_groups = red.n_groups; 2395 2396 mm_sat_prob_t<USE_PICO> mm_pb(n_classes, n_env, n_red); 2397 2398 auto& lm = mm_pb.lm; 2399 2400 // Creating sxi 2401 lm.unfreeze_xi(); 2402 2403 // Modif: literals sxi that correspond to the founding state of 2404 // a partial solution class are always true -> we therefore skip them 2405 2406 // 1 Set the partial solution 2407 // Each partial solution state gets its own class 2408 // This is a simple "true" variable, so omitted 2409 2410 // 2 State cover 2411 // Each state that is not a partial solution 2412 // must be in some class 2413 // Partial solution classes are skipped if incompatible 2414 const auto& is_psol = psol.is_psol; 2415 2416 for (unsigned s = 0; s < n_env; ++s) 2417 { 2418 if (is_psol[s] != -1u) 2419 continue; 2420 // new clause 2421 mm_pb.state_cover_clauses.emplace_back(std::piecewise_construct, 2422 std::forward_as_tuple(s), 2423 std::forward_as_tuple(std::vector<int>{})); 2424 auto& clause = mm_pb.state_cover_clauses.back().second; 2425 // All possible classes 2426 // Note, here they are all partial solutions 2427 for (unsigned i = 0; i < n_classes; ++i) 2428 if (!incompmat.get(psolv[i], s)) 2429 clause.push_back(lm.sxi2lit({s, i})); 2430 } 2431 // All sxi of importance, i.e. that can be true or false, 2432 // have been created 2433 lm.freeze_xi(); 2434 2435 // 3 Incomp 2436 // Modif: do not add partial solution 2437 // as the corresponding sxi does not appear in the cover 2438 // Note: special care is taken later on for closure 2439 trace << "c Incompatibility" << std::endl; 2440 { 2441 std::vector<int> inc_clause_(3); 2442 inc_clause_[2] = 0; 2443 for (unsigned x = 0; x < n_env; ++x) 2444 { 2445 for (unsigned i = 0; i < n_classes; ++i) 2446 { 2447 // Check if compatible with partial solution 2448 if (psolv[i] == x || incompmat.get(psolv[i], x)) 2449 continue; 2450 // Get all the incompatible states 2451 for (unsigned y = x + 1; y < n_env; ++y) 2452 { 2453 // Check if compatible with partial solution 2454 if (psolv[i] == y || incompmat.get(psolv[i], y)) 2455 continue; 2456 if (incompmat.get(x, y)) 2457 { 2458 inc_clause_[0] = -lm.sxi2lit({x, i}); 2459 inc_clause_[1] = -lm.sxi2lit({y, i}); 2460 mm_pb.add_static(inc_clause_); 2461 trace_clause(inc_clause_); 2462 } 2463 } 2464 } 2465 } 2466 } 2467 2468 2469 // 4 Cover for transitions 2470 // Modif if target or source are not compatible with 2471 // the partial solution class -> simplify condition 2472 // List of possible successor classes 2473 std::vector<bool> succ_classes(n_classes); 2474 2475 // Loop over all minimal letters 2476 // We need a vector of iterators to make it efficient 2477 // Attention, all letters in the split_mmw are minimal letter, 2478 // not all states have necessarily edges for all letters 2479 // (In the case of ltlsynt they do but not in general) 2480 using edge_it_type = decltype(split_mmw->out(0).begin()); 2481 std::vector<std::pair<edge_it_type, edge_it_type>> edge_it; 2482 edge_it.reserve((unsigned) n_env/n_groups + 1); 2483 2484 // has_a_edge[i] stores if i has an edge under a 2485 // No? -> -1u 2486 // Yes? -> dst state 2487 // This has to be done group by group now 2488 2489 std::vector<unsigned> group_states_; 2490 // global class number + local founding state index 2491 std::vector<std::pair<unsigned, unsigned>> group_classes_; 2492 std::vector<unsigned> has_a_edge_; 2493 2494 for (unsigned group = 0; group < n_groups; ++group) 2495 { 2496 trace << "c Group " << group << " trans cond\n"; 2497 const unsigned n_letters_g = red.bisim_letters[group].size(); 2498 2499 group_states_.clear(); 2500 for (unsigned s = 0; s < n_env; ++s) 2501 if (red.which_group[s] == group) 2502 group_states_.push_back(s); 2503 const unsigned n_states_g_ = group_states_.size(); 2504 // All classes that have their founding state in 2505 // the current group 2506 group_classes_.clear(); 2507 for (unsigned src_class = 0; src_class < n_classes; ++src_class) 2508 if (red.which_group[psolv[src_class]] == group) 2509 { 2510 unsigned idx = 2511 find_first_index_of(group_states_, 2512 [&](unsigned s) 2513 {return s == psolv[src_class]; }); 2514 assert(idx != n_states_g_); 2515 group_classes_.emplace_back(src_class, idx); 2516 } 2517 edge_it.clear(); 2518 for (unsigned s : group_states_) 2519 edge_it.emplace_back(split_mmw->out(s).begin(), 2520 split_mmw->out(s).end()); 2521 2522 has_a_edge_.resize(n_states_g_); 2523 2524 for (unsigned abddidu = 0; abddidu < n_letters_g; ++abddidu) 2525 { 2526 const unsigned abdd_idx = 2527 red.bisim_letters[group][abddidu].front(); 2528 const bdd& abdd = red.minimal_letters_vec[group][abdd_idx]; 2529 const int abddid = abdd.id(); 2530 // Advance all iterators if necessary 2531 // also check if finished. 2532 // if all edges are treated we can stop 2533 // Drive by check if a exists in outs 2534 auto h_a_it = has_a_edge_.begin(); 2535 std::for_each(edge_it.begin(), edge_it.end(), 2536 [&abddid, &h_a_it](auto& eit) 2537 { 2538 *h_a_it = -1u; 2539 if ((eit.first != eit.second) 2540 && (eit.first->cond.id() < abddid)) 2541 ++eit.first; 2542 if ((eit.first != eit.second) 2543 && (eit.first->cond.id() == abddid)) 2544 *h_a_it = eit.first->dst; 2545 ++h_a_it; 2546 }); 2547 assert(h_a_it == has_a_edge_.end()); 2548 2549 // Loop over src classes, note all classes are partial solution 2550 // classes 2551 for (auto [src_class, fdx_idx] : group_classes_) 2552 { 2553 // Successor of the founding state under the current letter 2554 const unsigned fdx = group_states_[fdx_idx]; 2555 const unsigned fdx_succ = has_a_edge_[fdx_idx]; 2556 // -1u if not partial solution else number of class 2557 const unsigned fdx_succ_class = 2558 (fdx_succ == -1u) ? -1u : is_psol[fdx_succ]; 2559 2560 assert(!mm_pb.trans_cover_clauses.count({src_class, 2561 abddidu})); 2562 if (fdx_succ_class != -1u) 2563 { 2564 // The target is also partial solution state 2565 // -> fdx_succ_class is the only possible successor class 2566 assert(!lm.get_iaj({src_class, abddidu, fdx_succ_class})); 2567 lm.unfreeze_iaj(); 2568 int iajlit = lm.ziaj2lit({src_class, abddidu, 2569 fdx_succ_class}); 2570 lm.freeze_iaj(); 2571 mm_pb.trans_cover_clauses[{src_class, abddidu}] 2572 .push_back(iajlit); 2573 add_trans_cstr_f<USE_PICO>(mm_pb, 2574 incompmat, 2575 {src_class, abddidu, 2576 fdx_succ_class}, 2577 fdx_succ, iajlit, fdx_idx, 2578 group_states_, has_a_edge_); 2579 } 2580 else 2581 { 2582 // We need to determine all possible 2583 // successor classes 2584 // Note that fdx_succ (if existent) always has to be 2585 // in the target class, so only classes compatible 2586 // to this state are viable 2587 std::fill(succ_classes.begin(), succ_classes.end(), 2588 false); 2589 for (unsigned xidx = 0; xidx < n_states_g_; ++ xidx) 2590 { 2591 const unsigned x = group_states_[xidx]; 2592 // x comp src class 2593 if (incompmat.get(fdx, x)) 2594 continue; 2595 const unsigned xprime = has_a_edge_[xidx]; 2596 // xprime comp dst class 2597 if (xprime == -1u 2598 || (fdx_succ != -1u 2599 && incompmat.get(fdx_succ, xprime))) 2600 continue; 2601 bool added_dst = false; 2602 for (unsigned dst_class = 0; dst_class < n_classes; 2603 ++dst_class) 2604 { 2605 if (succ_classes[dst_class]) 2606 continue; 2607 if ((fdx_succ == -1u 2608 || !incompmat.get(psolv[dst_class], 2609 fdx_succ)) 2610 && !incompmat.get(psolv[dst_class], xprime)) 2611 { 2612 // Possible dst 2613 succ_classes[dst_class] = true; 2614 lm.unfreeze_iaj(); 2615 int iajlit = lm.ziaj2lit({src_class, abddidu, 2616 dst_class}); 2617 lm.freeze_iaj(); 2618 mm_pb.trans_cover_clauses[{src_class, 2619 abddidu}] 2620 .push_back(iajlit); 2621 add_trans_cstr_f(mm_pb, 2622 incompmat, 2623 {src_class, abddidu, 2624 dst_class}, 2625 psolv[dst_class], iajlit, 2626 fdx_idx, group_states_, 2627 has_a_edge_); 2628 added_dst = true; 2629 } 2630 } 2631 if (added_dst && all_of(succ_classes)) 2632 break; 2633 } // All source states -> possible dst 2634 } // founding state -> founding state? 2635 }//src_class 2636 } // letter 2637 // check if all have been used 2638 assert(std::all_of(edge_it.begin(), edge_it.end(), 2639 [](auto& eit) 2640 { 2641 return ((eit.first == eit.second) 2642 || ((++eit.first) == eit.second)); 2643 })); 2644 } // group 2645 // Done building the initial problem 2646 trace << std::endl; 2647 2648 // we also have to init the helper struct 2649 mm_pb.ocond_maps.resize(red.n_groups); 2650 for (unsigned i = 0; i < red.n_groups; ++i) 2651 mm_pb.ocond_maps[i].resize(red.minimal_letters_vec[i].size()); 2652 mm_pb.tracked_s_pair = square_matrix<bool, true>(n_env, false); 2653 2654 return mm_pb; 2655 } 2656 2657 // This is called when we increase the number of available classes 2658 // We know that the new class is not associated to a partial solution 2659 // or founding state 2660 template <bool USE_PICO> increment_classes(const_twa_graph_ptr split_mmw,const square_matrix<bool,true> & incompmat,const reduced_alphabet_t & red,const part_sol_t & psol,mm_sat_prob_t<USE_PICO> & mm_pb)2661 void increment_classes(const_twa_graph_ptr split_mmw, 2662 const square_matrix<bool, true>& incompmat, 2663 const reduced_alphabet_t& red, 2664 const part_sol_t& psol, 2665 mm_sat_prob_t<USE_PICO>& mm_pb) 2666 { 2667 const unsigned new_class = mm_pb.n_classes++; 2668 const unsigned n_env = mm_pb.lm.n_env_; 2669 auto& lm = mm_pb.lm; 2670 const auto& psolv = psol.psol; 2671 const unsigned n_psol = psolv.size(); 2672 const unsigned n_groups = red.n_groups; 2673 2674 2675 // 1 Add the new class to all states that are not founding states 2676 // Note that in the other case, we still have to create the 2677 // literal eventually, as it might be needed for the transition conditions 2678 auto it_cc = mm_pb.state_cover_clauses.begin(); 2679 lm.unfreeze_xi(); 2680 for (unsigned x = 0; x < n_env; ++x) 2681 { 2682 if (psol.is_psol[x] != -1u) 2683 // Partial solution state 2684 continue; 2685 assert(it_cc != mm_pb.state_cover_clauses.end()); 2686 it_cc->second.push_back(lm.sxi2lit({x, new_class})); 2687 ++it_cc; 2688 } 2689 assert(it_cc == mm_pb.state_cover_clauses.end()); 2690 2691 2692 // 2 Set incompatibilities 2693 // All states can be in the new class, so we have to set all 2694 // incompatibilities 2695 { 2696 trace << "c Incomp class " << new_class << '\n'; 2697 std::vector<int> inc_clause_(3); // Vector call to pico faster 2698 inc_clause_[2] = 0; 2699 for (unsigned x = 0; x < n_env; ++x) 2700 { 2701 assert(lm.get_sxi({x, new_class}) || psol.is_psol[x] != -1u); 2702 for (unsigned y = x + 1; y < n_env; ++y) 2703 if (incompmat.get(x, y)) 2704 { 2705 assert(lm.get_sxi({y, new_class}) || psol.is_psol[y] != -1u); 2706 inc_clause_[0] = -lm.sxi2lit({x, new_class}); 2707 inc_clause_[1] = -lm.sxi2lit({y, new_class}); 2708 mm_pb.add_static(inc_clause_); 2709 trace_clause(inc_clause_); 2710 } 2711 } 2712 } 2713 2714 // 3 Transition cover 2715 // Add the new class to the cover condition of 2716 // transitions 2717 // Note that all classes are possible targets of the new 2718 // class and all classes can target the new class 2719 // Note all classes means also all groups 2720 // so we need all minimal letters 2721 lm.unfreeze_iaj(); 2722 // New_class as dst 2723 for (auto& elem : mm_pb.trans_cover_clauses) 2724 elem.second.push_back(lm.ziaj2lit({elem.first.first, elem.first.second, 2725 new_class})); 2726 // New_class as src 2727 for (unsigned abddidu = 0; abddidu < red.n_red_sigma; ++abddidu) 2728 { 2729 auto& na_cover = 2730 mm_pb.trans_cover_clauses[{new_class, abddidu}]; 2731 na_cover.reserve(new_class + 1); 2732 for (unsigned dst_class = 0; dst_class <= new_class; ++dst_class) 2733 na_cover.push_back(lm.ziaj2lit({new_class, abddidu, dst_class})); 2734 } 2735 lm.freeze_iaj(); 2736 2737 2738 // 4 Transition 2739 // As before, simplify conditions 2740 // we need to loop through all letters again 2741 using edge_it_type = decltype(split_mmw->out(0).begin()); 2742 static std::vector<std::pair<edge_it_type, edge_it_type>> edge_it; 2743 edge_it.reserve((unsigned) n_env/n_groups + 1); 2744 2745 // has_a_edge[i] stores if i has an edge under a 2746 // No? -> -1u 2747 // Yes? -> dst state 2748 // This has to be done group by group now 2749 2750 static std::vector<unsigned> group_states_; 2751 static std::vector<unsigned> has_a_edge_; 2752 2753 for (unsigned group = 0; group < n_groups; ++group) 2754 { 2755 trace << "c Trans conditions group " << group << '\n'; 2756 const unsigned n_letters_g = red.bisim_letters[group].size(); 2757 2758 group_states_.clear(); 2759 for (unsigned s = 0; s < n_env; ++s) 2760 if (red.which_group[s] == group) 2761 group_states_.push_back(s); 2762 const unsigned n_states_g_ = group_states_.size(); 2763 edge_it.clear(); 2764 for (unsigned s : group_states_) 2765 edge_it.emplace_back(split_mmw->out(s).begin(), 2766 split_mmw->out(s).end()); 2767 2768 has_a_edge_.resize(n_states_g_); 2769 2770 for (unsigned abddidu = 0; abddidu < n_letters_g; ++abddidu) 2771 { 2772 const unsigned abdd_idx = 2773 red.bisim_letters[group][abddidu].front(); 2774 const bdd& abdd = red.minimal_letters_vec[group][abdd_idx]; 2775 const int abddid = abdd.id(); 2776 // Advance all iterators if necessary 2777 // also check if finished. 2778 // if all edges are treated we can stop 2779 // Drive by check if a exists in outs 2780 auto h_a_it = has_a_edge_.begin(); 2781 std::for_each(edge_it.begin(), edge_it.end(), 2782 [&abddid, &h_a_it](auto& eit) 2783 { 2784 *h_a_it = -1u; 2785 if ((eit.first != eit.second) 2786 && (eit.first->cond.id() < abddid)) 2787 ++eit.first; 2788 if ((eit.first != eit.second) 2789 && (eit.first->cond.id() == abddid)) 2790 *h_a_it = eit.first->dst; 2791 ++h_a_it; 2792 }); 2793 assert(h_a_it == has_a_edge_.end()); 2794 2795 // All other classes 2796 // Loop over all states of the group 2797 std::vector<int> inc_clause(4, 0); 2798 for (unsigned xidx = 0; xidx < n_states_g_; ++xidx) 2799 { 2800 const unsigned x = group_states_[xidx]; 2801 const unsigned xprime = has_a_edge_[xidx]; 2802 if (xprime == -1u) 2803 continue; // No edge here 2804 2805 // New class as dst 2806 // All transitions can go 2807 // but not all transitions can start in any class 2808 // Note that it can also go to it self hence the <= 2809 // Important the literal sxi is simply true for x <-> i 2810 // a) x is incompatible with partial solution -> skip 2811 // b) x is the founding state of the src class 2812 // -> then it is always in the class 2813 // c) x can possibly be in the src class 2814 for (unsigned src_class = 0; src_class <= new_class; 2815 ++src_class) 2816 { 2817 // a) 2818 if ((src_class < n_psol) 2819 && incompmat.get(x, psolv[src_class])) 2820 // x can not be in source class 2821 // No additional constraints necessary 2822 continue; 2823 // the iaj 2824 inc_clause[0] = -lm.ziaj2lit({src_class, abddidu, 2825 new_class}); 2826 2827 // The next two sxi2lit can introduce new literals 2828 // all states can possibly be in the new class 2829 inc_clause[1] = lm.sxi2lit({xprime, new_class}); 2830 2831 // x is not in src class. 2832 // This is not possible if x is founding state 2833 if (src_class < n_psol && psolv[src_class] == x) 2834 // b) Founding state 2835 inc_clause[2] = 0; 2836 else 2837 // c) Full condition 2838 inc_clause[2] = -lm.sxi2lit({x, src_class}); 2839 2840 trace_clause(inc_clause); 2841 mm_pb.add_static(inc_clause); 2842 }//src classes 2843 // New class as src 2844 // all states can be in there, but not all targets must 2845 // be compatible 2846 // "self-loop" already covered 2847 // Note: If the dst is a partial solution class then 2848 // a) xprime is a founding state 2849 // b) The xprime is incompatible with the founding state 2850 // -> -sxi || -ziaj 2851 // the clause -sxi || -ziaj || sxprimej is trivially fulfilled 2852 // c) All other cases -> full clause 2853 2854 for (unsigned dst_class = 0; dst_class < new_class; 2855 ++dst_class) 2856 { 2857 if (dst_class < n_psol && psolv[dst_class] == xprime) 2858 continue; // case a) 2859 2860 // case b) 2861 inc_clause[0] = -lm.sxi2lit({x, new_class}); 2862 inc_clause[1] = -lm.ziaj2lit({new_class, abddidu, 2863 dst_class}); 2864 // Adding lit to go from b) to c) 2865 if (dst_class < n_psol 2866 && incompmat.get(xprime, psolv[dst_class])) 2867 inc_clause[2] = 0; 2868 else 2869 { 2870 int sxi = lm.sxi2lit({xprime, dst_class}); 2871 assert(sxi); 2872 inc_clause[2] = sxi; 2873 } 2874 2875 trace_clause(inc_clause); 2876 mm_pb.add_static(inc_clause); 2877 }// dst calsses 2878 } // states 2879 } // letters 2880 } // groups 2881 lm.freeze_xi(); 2882 2883 // "Propagate" the knowledge about cases 2884 // where the usual constraints are insufficient to cope with 2885 // the expressiveness of bdds 2886 // All constraints on the cube(s) are conditioned by 2887 // whether or not the states share some class ixy 2888 // So here we only need to add the new class to all 2889 // tracked states. 2890 std::vector<int> c_clause(4, 0); 2891 const auto& lm_c = lm; 2892 // The state literals must exist 2893 for (unsigned s1 = 0; s1 < n_env; ++s1) 2894 for (unsigned s2 = s1 + 1; s2 < n_env; ++s2) 2895 if (mm_pb.tracked_s_pair.get(s1, s2)) 2896 { 2897 c_clause[0] = -lm.sxi2lit({s1, new_class}); 2898 c_clause[1] = -lm_c.sxi2lit({s2, new_class}); 2899 c_clause[2] = lm_c.ixy2lit({s1, s2}); 2900 } 2901 } // done increment_classes 2902 2903 std::vector<std::vector<bdd>> comp_represented_cond(const reduced_alphabet_t & red)2904 comp_represented_cond(const reduced_alphabet_t& red) 2905 { 2906 const unsigned n_groups = red.n_groups; 2907 // For each minimal letter, create the (input) condition that it represents 2908 // This has to be created for each minimal letters 2909 // and might be shared between alphabets 2910 std::vector<std::vector<bdd>> gmm2cond; 2911 gmm2cond.reserve(n_groups); 2912 for (unsigned group = 0; group < n_groups; ++group) 2913 { 2914 const unsigned n_sigma = red.share_sigma_with[group]; 2915 if (n_sigma == group) 2916 { 2917 // New alphabet, construct all the conditions 2918 const unsigned size_sigma = red.minimal_letters_vec[group].size(); 2919 gmm2cond.push_back(std::vector<bdd>(size_sigma, bddfalse)); 2920 for (unsigned idx = 0; idx < size_sigma; ++idx) 2921 { 2922 // We need to actually construct it 2923 bdd repr = red.minimal_letters_vec[group][idx]; 2924 const auto& [_, repr_letters] = 2925 red.minimal_letters[group].at(repr); 2926 // The class of letters is the first set 2927 for (int id : repr_letters) 2928 { 2929 bdd idbdd = bdd_from_int(id); 2930 gmm2cond.back()[idx] |= idbdd; 2931 } 2932 } 2933 } 2934 else 2935 { 2936 // Copy 2937 assert(n_sigma < group); 2938 gmm2cond.push_back(gmm2cond.at(n_sigma)); 2939 } 2940 } 2941 return gmm2cond; 2942 } 2943 cstr_split_mealy(twa_graph_ptr & minmach,const reduced_alphabet_t & red,const std::vector<std::pair<unsigned,std::vector<bool>>> & x_in_class,std::unordered_map<iaj_t,bdd,decltype(iaj_hash),decltype(iaj_eq)> & used_ziaj_map)2944 void cstr_split_mealy(twa_graph_ptr& minmach, 2945 const reduced_alphabet_t& red, 2946 const std::vector<std::pair<unsigned, 2947 std::vector<bool>>>& 2948 x_in_class, 2949 std::unordered_map<iaj_t, bdd, 2950 decltype(iaj_hash), 2951 decltype(iaj_eq)>& used_ziaj_map) 2952 { 2953 const unsigned n_env_states = minmach->num_states(); 2954 // For each minimal letter, create the (input) condition that it represents 2955 // This has to be created for each minimal letters 2956 // and might be shared between alphabets 2957 std::vector<std::vector<bdd>> gmm2cond 2958 = comp_represented_cond(red); 2959 2960 #ifdef TRACE 2961 for (const auto& el : used_ziaj_map) 2962 { 2963 const unsigned group = x_in_class[el.first.i].first; 2964 const bdd& incond = gmm2cond[group][el.first.a]; 2965 std::cerr << el.first.i << " - " << incond << " / " 2966 << el.second << " > " << el.first.j << std::endl; 2967 } 2968 #endif 2969 2970 // player_state_map 2971 // xi.x -> dst class 2972 // xi.i -> id of outcond 2973 // value -> player state 2974 std::unordered_map<xi_t, unsigned, pair_hash> player_state_map; 2975 player_state_map.reserve(minmach->num_states()); 2976 auto get_player = [&](unsigned dst_class, const bdd& outcond) 2977 { 2978 auto [it, inserted] = 2979 player_state_map.try_emplace({dst_class, (unsigned) outcond.id()}, 2980 -1u); 2981 if (inserted) 2982 { 2983 it->second = minmach->new_state(); 2984 minmach->new_edge(it->second, dst_class, outcond); 2985 trace << "Added p " << it->second << " - " << outcond << " > " 2986 << dst_class << std::endl; 2987 } 2988 assert(it->second < minmach->num_states()); 2989 return it->second; 2990 }; 2991 2992 // env_edge_map 2993 // xi.x -> src_class 2994 // xi.i -> player state 2995 // value -> edge_number 2996 std::unordered_map<xi_t, unsigned, pair_hash> env_edge_map; 2997 env_edge_map.reserve(minmach->num_states()); 2998 2999 auto add_edge = [&](unsigned src_class, unsigned dst_class, 3000 const bdd& incond, const bdd& outcond) 3001 { 3002 unsigned p_state = get_player(dst_class, outcond); 3003 auto it = env_edge_map.find({src_class, p_state}); 3004 if (it == env_edge_map.end()) 3005 { 3006 // Construct the edge 3007 env_edge_map[{src_class, p_state}] = 3008 minmach->new_edge(src_class, p_state, incond); 3009 trace << "Added e " << src_class << " - " << incond << " > " 3010 << p_state << std::endl; 3011 } 3012 else 3013 // There is already an edge from src to pstate -> or the condition 3014 minmach->edge_storage(it->second).cond |= incond; 3015 }; 3016 3017 for (const auto& [iaj, outcond] : used_ziaj_map) 3018 { 3019 // The group determines the incond 3020 const unsigned group = x_in_class[iaj.i].first; 3021 const bdd& incond = gmm2cond[group][iaj.a]; 3022 add_edge(iaj.i, iaj.j, incond, outcond); 3023 } 3024 3025 // Set the state-player 3026 auto* sp = new std::vector<bool>(minmach->num_states(), true); 3027 for (unsigned i = 0; i < n_env_states; ++i) 3028 (*sp)[i] = false; 3029 minmach->set_named_prop("state-player", sp); 3030 } 3031 3032 // This function refines the sat constraints in case the 3033 // incompatibility computation relying on bdds is too optimistic 3034 // It add constraints for each violating class and letter 3035 template <bool USE_PICO> add_bdd_cond_constr(mm_sat_prob_t<USE_PICO> & mm_pb,const_twa_graph_ptr mmw,const reduced_alphabet_t & red,const unsigned n_env,const std::deque<std::pair<unsigned,unsigned>> & infeasible_classes,const std::vector<std::pair<unsigned,std::vector<bool>>> & x_in_class)3036 void add_bdd_cond_constr(mm_sat_prob_t<USE_PICO>& mm_pb, 3037 const_twa_graph_ptr mmw, 3038 const reduced_alphabet_t& red, 3039 const unsigned n_env, 3040 const std::deque<std::pair<unsigned, unsigned>>& 3041 infeasible_classes, 3042 const std::vector<std::pair<unsigned, 3043 std::vector<bool>>>& 3044 x_in_class) 3045 { 3046 //infeasible_classes : Class, Letter index 3047 const unsigned n_groups = red.n_groups; 3048 3049 // Step one: Decompose all concerned conditions 3050 // that have not yet been decomposed 3051 decltype(mm_pb.ocond_maps) ocond_maps(n_groups); 3052 for (unsigned i = 0; i < n_groups; ++i) 3053 ocond_maps[i].resize(red.minimal_letters_vec[i].size()); 3054 3055 // Helper 3056 auto get_o_cond = [&](const auto& e) 3057 { 3058 return mmw->out(e.dst).begin()->cond; 3059 }; 3060 for (auto [n_class, letter_idx] : infeasible_classes) 3061 { 3062 trace << "c Adding additional constraints for class " 3063 << n_class << " and letter id " << letter_idx << '\n'; 3064 const unsigned group = red.which_group[x_in_class[n_class].first]; 3065 // Check all states in this class if already decomposed 3066 for (unsigned s = 0; s < n_env; ++s) 3067 { 3068 // In class? 3069 if (!x_in_class[group].second[s]) 3070 continue; 3071 // Decomposed? 3072 // Note the set is only ordered with respect to the state, 3073 // so it does not matter which bdd we use to check if the 3074 // outcond of the minimal letter and is already decomposed 3075 if (mm_pb.ocond_maps.at(group).at(letter_idx).count({s, bddfalse})) 3076 continue; 3077 3078 // Search for the actual edge implied by this minimal letter 3079 // there is only one 3080 const auto& impl_edges = 3081 red.minimal_letters.at(group). 3082 at(red.minimal_letters_vec.at(group).at(letter_idx)).first; 3083 bdd econd = bddfalse; 3084 for (const auto& e : mmw->out(s)) 3085 if (impl_edges.count(e.cond.id())) 3086 { 3087 assert(econd == bddfalse); 3088 econd = get_o_cond(e); 3089 #ifdef NDEBUG 3090 break; 3091 #endif 3092 } 3093 // Safe it 3094 assert(econd != bddfalse); 3095 ocond_maps[group][letter_idx].emplace(s, econd); 3096 // Check if this bdd (econd) was already decomposed earlier on 3097 // If not, do so 3098 // Decompose it into cubes 3099 auto [it, inserted] = 3100 mm_pb.cube_map.try_emplace(econd.id(), 3101 std::vector<bdd>()); 3102 3103 if (inserted) 3104 { 3105 minato_isop econd_isop(econd); 3106 bdd prod; 3107 while ((prod = econd_isop.next()) != bddfalse) 3108 it->second.push_back(prod); 3109 } 3110 } 3111 } 3112 // Decomposed all newly discovered conflicts 3113 3114 // Compute the literals and clauses 3115 // of the new cases 3116 // 1) Covering condition for conditions that have more than one cube 3117 auto& lm = mm_pb.lm; 3118 std::vector<int> c_clause; 3119 for (unsigned group = 0; group < n_groups; ++group) 3120 { 3121 const auto& group_map = ocond_maps[group]; 3122 const unsigned n_ml = red.minimal_letters_vec[group].size(); 3123 for (unsigned letter_idx = 0; letter_idx < n_ml; ++letter_idx) 3124 { 3125 const auto& ml_list = group_map[letter_idx]; 3126 for (const auto& [s, econd] : ml_list) 3127 { 3128 const unsigned n_cubes = mm_pb.cube_map.at(econd.id()).size(); 3129 assert(n_cubes); 3130 c_clause.clear(); 3131 for (unsigned idx = 0; idx < n_cubes; ++idx) 3132 c_clause.push_back(lm.cuxk2lit({letter_idx, s, idx})); 3133 c_clause.push_back(0); 3134 mm_pb.add_static(c_clause); 3135 trace_clause(c_clause); 3136 } 3137 } 3138 } 3139 3140 // 2) Incompatibility condition between cubes 3141 // If a condition has only one cube -> use the state 3142 // Attention lm.get(sxi) returns zero if x is the founding state of i 3143 // Incompatibilities can arise between new/new and new/old conditions 3144 // Avoid redundant clauses for new/new constraints new/new 3145 auto create_cstr = [&](unsigned s1, unsigned s2, 3146 const std::vector<std::pair<int, int>>& 3147 incomp_cubes_list) 3148 { 3149 // No simplification as this can backfire 3150 3151 // Helper literal that determines if s1 and s2 are 3152 // at least in one common class 3153 // either s1 is not in class or s2 is not in class 3154 // ot is1s2 3155 const int is1s2 = lm.ixy2lit({s1, s2}); 3156 // The constraint below is might have already been 3157 // constructed if so, the states are marked as tracked 3158 if (!mm_pb.tracked_s_pair.get(s1, s2)) 3159 { 3160 mm_pb.tracked_s_pair.set(s1, s2, true); 3161 for (unsigned iclass = 0; iclass < mm_pb.n_classes; ++iclass) 3162 { 3163 c_clause.clear(); 3164 int c_lit; 3165 c_lit = lm.get_sxi({s1, iclass}); 3166 if (c_lit) 3167 c_clause.push_back(-c_lit); 3168 c_lit = lm.get_sxi({s2, iclass}); 3169 if (c_lit) 3170 c_clause.push_back(-c_lit); 3171 c_clause.push_back(is1s2); 3172 c_clause.push_back(0); 3173 mm_pb.add_static(c_clause); 3174 trace_clause(c_clause); 3175 } 3176 } 3177 // Now all the additional clauses have the form 3178 // not same class or not cube1 or not cube2 3179 c_clause.resize(4); 3180 std::fill(c_clause.begin(), c_clause.end(), 0); 3181 c_clause[0] = -is1s2; 3182 for (auto [c1_lit, c2_lit] : incomp_cubes_list) 3183 { 3184 c_clause[1] = -c1_lit; 3185 c_clause[2] = -c2_lit; 3186 mm_pb.add_static(c_clause); 3187 trace_clause(c_clause); 3188 } 3189 }; 3190 3191 auto fill_incomp_list = [&](std::vector<std::pair<int, int>>& 3192 incomp_cubes_list, 3193 unsigned letter_idx, 3194 unsigned s1, const std::vector<bdd>& c_list1, 3195 unsigned s2, const std::vector<bdd>& c_list2) 3196 { 3197 const unsigned n_c1 = c_list1.size(); 3198 const unsigned n_c2 = c_list2.size(); 3199 incomp_cubes_list.clear(); 3200 for (unsigned c1_idx = 0; c1_idx < n_c1; ++c1_idx) 3201 for (unsigned c2_idx = 0; c2_idx < n_c2; ++c2_idx) 3202 { 3203 auto [it, inserted] = 3204 mm_pb.cube_incomp_map.try_emplace({c_list1[c1_idx].id(), 3205 c_list2[c2_idx].id()}, 3206 false); 3207 if (inserted) 3208 it->second = 3209 bdd_have_common_assignment(c_list1[c1_idx], 3210 c_list2[c2_idx]); 3211 if (!it->second) 3212 incomp_cubes_list.emplace_back((int) c1_idx, 3213 (int) c2_idx); 3214 } 3215 3216 // Replace the indices in the incomp_cubes_list 3217 // with the literals if there is more than one cube the 3218 // reduce the number of look-ups 3219 auto repl1 = [&, ntrans = n_c1 == 1](int idx) 3220 { 3221 return ntrans ? idx : lm.cuxk2lit({letter_idx, 3222 s1, 3223 (unsigned) idx}); 3224 }; 3225 auto repl2 = [&, ntrans = n_c2 == 1](int idx) 3226 { 3227 return ntrans ? idx : lm.cuxk2lit({letter_idx, 3228 s2, 3229 (unsigned) idx}); 3230 }; 3231 std::transform(incomp_cubes_list.begin(), 3232 incomp_cubes_list.end(), 3233 incomp_cubes_list.begin(), 3234 [&](auto& el) -> std::pair<int, int> 3235 {return {repl1(el.first), 3236 repl2(el.second)}; }); 3237 }; 3238 3239 std::vector<std::pair<int, int>> incomp_cubes_list; 3240 for (unsigned group = 0; group < n_groups; ++group) 3241 { 3242 const auto& group_map = ocond_maps[group]; 3243 const unsigned n_ml = red.minimal_letters_vec[group].size(); 3244 for (unsigned letter_idx = 0; letter_idx < n_ml; ++letter_idx) 3245 { 3246 const auto& ml_list = group_map[letter_idx]; 3247 // Incompatibility is commutative 3248 // new / new constraints 3249 const auto it_end = ml_list.end(); 3250 const auto it_endm1 = --ml_list.end(); 3251 for (auto it1 = ml_list.begin(); it1 != it_endm1; ++it1) 3252 { 3253 auto it2 = it1; 3254 ++it2; 3255 for (; it2 != it_end; ++it2) 3256 { 3257 const auto& [s1, oc1] = *it1; 3258 const auto& [s2, oc2] = *it2; 3259 const auto& c_list1 = mm_pb.cube_map.at(oc1.id()); 3260 const unsigned n_c1 = c_list1.size(); 3261 const auto& c_list2 = mm_pb.cube_map.at(oc2.id()); 3262 const unsigned n_c2 = c_list2.size(); 3263 3264 // If both of them only have one cube the base constraints 3265 // are sufficient 3266 if (n_c1 == 1 && n_c2 == 1) 3267 continue; 3268 // The simplified condition is also correct if 3269 // every cube of s1 intersects with every cube of s2 3270 // Build a list of incompatible cubes 3271 fill_incomp_list(incomp_cubes_list, letter_idx, 3272 s1, c_list1, s2, c_list2); 3273 3274 if (incomp_cubes_list.empty()) 3275 continue; 3276 3277 create_cstr(s1, s2, incomp_cubes_list); 3278 } 3279 } 3280 // New / old constraints 3281 // We need to add constraints between newly decomposed 3282 // letter/states combinations with the ones already found 3283 const auto& ml_list_old = mm_pb.ocond_maps[group][letter_idx]; 3284 for (const auto& [s1, oc1] : ml_list) 3285 for (const auto& [s2, oc2] : ml_list_old) 3286 { 3287 const auto& c_list1 = mm_pb.cube_map.at(oc1.id()); 3288 const unsigned n_c1 = c_list1.size(); 3289 const auto& c_list2 = mm_pb.cube_map.at(oc2.id()); 3290 const unsigned n_c2 = c_list2.size(); 3291 3292 if (n_c1 == 1 && n_c2 == 1) 3293 continue; 3294 3295 fill_incomp_list(incomp_cubes_list, letter_idx, 3296 s1, c_list1, s2, c_list2); 3297 3298 if (incomp_cubes_list.empty()) 3299 continue; 3300 3301 create_cstr(s1, s2, incomp_cubes_list); 3302 } 3303 } 3304 } 3305 // Done creating the additional constraints 3306 } 3307 3308 template<bool USE_PICO> 3309 twa_graph_ptr try_build_min_machine(mm_sat_prob_t<USE_PICO> & mm_pb,const_twa_graph_ptr mmw,const reduced_alphabet_t & red,const part_sol_t & psol,const unsigned n_env,stopwatch & sw)3310 try_build_min_machine(mm_sat_prob_t<USE_PICO>& mm_pb, 3311 const_twa_graph_ptr mmw, 3312 const reduced_alphabet_t& red, 3313 const part_sol_t& psol, 3314 const unsigned n_env, 3315 stopwatch& sw) 3316 { 3317 const auto& psolv = psol.psol; 3318 const unsigned n_psol = psolv.size(); 3319 const unsigned n_groups = red.n_groups; 3320 3321 // List of incompatible/infeasible classes and letters 3322 // first class, second minimal letter 3323 std::deque<std::pair<unsigned, unsigned>> infeasible_classes; 3324 3325 // Check if a solution exists for the current prob 3326 // Add the variable clauses 3327 // looks daring but we either find a solution or it is infeasible 3328 // in both cases we return directly 3329 while (true) 3330 { 3331 infeasible_classes.clear(); 3332 #ifdef TRACE 3333 mm_pb.lm.print(std::cerr); 3334 #endif 3335 mm_pb.set_variable_clauses(); 3336 dotimeprint << "Done constructing SAT " << sw.stop() << '\n'; 3337 dotimeprint << "n literals " << mm_pb.n_lits() 3338 << " n clauses " << mm_pb.n_clauses() << '\n'; 3339 auto sol = mm_pb.get_sol(); 3340 dotimeprint << "Done solving SAT " << sw.stop() << '\n'; 3341 3342 if (sol.empty()) 3343 { 3344 mm_pb.unset_variable_clauses(); 3345 return nullptr; 3346 } 3347 #ifdef TRACE 3348 mm_pb.lm.print(std::cerr, &sol); 3349 #endif 3350 3351 const unsigned n_classes = mm_pb.n_classes; 3352 const auto& lm = mm_pb.lm; 3353 3354 auto minmach = make_twa_graph(mmw->get_dict()); 3355 minmach->copy_ap_of(mmw); 3356 3357 // We have as many states as classes 3358 // Plus the state necessary for player states if 3359 // we do not unsplit 3360 minmach->new_states(n_classes); 3361 3362 // Get the init state 3363 unsigned x_init = mmw->get_init_state_number(); 3364 trace << "orig init " << x_init << '\n'; 3365 std::vector<unsigned> init_class_v; 3366 assert(x_init < n_env); 3367 { 3368 trace << "List of init classes "; 3369 if (psol.is_psol[x_init] != -1u) 3370 init_class_v.push_back(psol.is_psol[x_init]); 3371 for (unsigned i = 0; i < n_classes; ++i) 3372 { 3373 int litsxi = lm.get_sxi({x_init, i}); 3374 if (litsxi && (sol.at(litsxi) == 1)) 3375 { 3376 init_class_v.push_back(i); 3377 trace << i << " -> "<< litsxi << " : " << sol.at(litsxi) 3378 << std::endl; 3379 } 3380 } 3381 assert(!init_class_v.empty()); 3382 } 3383 3384 // Save which class has which states 3385 // and to which group this class belongs 3386 std::vector<std::pair<unsigned, std::vector<bool>>> 3387 x_in_class(n_classes, 3388 std::make_pair(-1u, std::vector<bool>(n_env, false))); 3389 3390 // Todo : Check if we can "reduce" the solution 3391 // that is to remove states from classes without 3392 // violating the constraints. 3393 // Idea: Less constraints to encode -> smaller AIGER for syntcomp 3394 3395 // Add partial solution state 3396 for (unsigned i = 0; i < n_classes; ++i) 3397 { 3398 for (unsigned x = 0; x < n_env; ++x) 3399 // By convention 0-lit is false 3400 x_in_class[i].second[x] = 3401 (sol.at(lm.get_sxi({x, i})) == 1); 3402 if (i < n_psol) 3403 // partial solution 3404 x_in_class[i].second[psolv[i]] = true; 3405 unsigned first_x = find_first_index_of(x_in_class[i].second); 3406 assert(first_x != n_env && "No state in class."); 3407 x_in_class[i].first = red.which_group[first_x]; 3408 } 3409 #ifdef TRACE 3410 for (unsigned i = 0; i < n_classes; ++i) 3411 { 3412 trace << "Class " << i << " group " << x_in_class[i].first << '\n'; 3413 for (unsigned x = 0; x < n_env; ++x) 3414 if (x_in_class[i].second[x]) 3415 trace << x << ' '; 3416 trace << std::endl; 3417 } 3418 #endif 3419 3420 // Check that each class has only states of the same group 3421 assert(std::all_of(x_in_class.begin(), x_in_class.end(), 3422 [&red, n_env](const auto& p) 3423 { 3424 for (unsigned i = 0; i < n_env; ++i) 3425 if (p.second[i] 3426 && (red.which_group[i] != p.first)) 3427 { 3428 trace << "state " 3429 << i << " is in a class " 3430 "associated to group " 3431 << p.first << std::endl; 3432 return false; 3433 } 3434 return true; 3435 })); 3436 3437 // Build the conditions 3438 // Decide on which ziaj to use 3439 std::unordered_map<iaj_t, bdd, decltype(iaj_hash), decltype(iaj_eq)> 3440 used_ziaj_map(0, iaj_hash, iaj_eq); 3441 used_ziaj_map.reserve(1 + lm.ziaj_map_.size()/2); 3442 3443 // todo : Here we use the first successor found. 3444 // Better ideas? 3445 // Note ziaj : class i goes to j for minimal bisimilar letter a. 3446 // a represents a number of minimal letters -> all of them 3447 // make i go to j 3448 for (unsigned src_class = 0; src_class < n_classes; ++src_class) 3449 { 3450 const unsigned group = x_in_class[src_class].first; 3451 const unsigned n_mlb = red.bisim_letters[group].size(); 3452 for (unsigned amlbidu = 0; amlbidu < n_mlb; ++amlbidu) 3453 { 3454 for (unsigned dst_class = 0; dst_class < n_classes; ++dst_class) 3455 if (sol.at(lm.get_iaj({src_class, amlbidu, dst_class})) == 1) 3456 { 3457 trace << "using mlb " << src_class << ' ' << amlbidu 3458 << ' ' << dst_class << std::endl; 3459 //Accept this for all bisimilar 3460 for (unsigned abddidu : red.bisim_letters[group][amlbidu]) 3461 { 3462 used_ziaj_map[{src_class, abddidu, dst_class}] 3463 = bddtrue; 3464 trace << "using " << src_class << ' ' << abddidu 3465 << ' ' << dst_class << std::endl; 3466 } 3467 break; 3468 } 3469 } 3470 } 3471 // todo check for no trans? 3472 // Attention, from here we treat the minimal letters 3473 // not the bisimilar ones, as minimal letters share outconds, which is 3474 // not the case for bisimilar ones 3475 3476 // Loop over edges to construct the out conds 3477 auto get_o_cond = [&](const auto& e) 3478 { 3479 return mmw->out(e.dst).begin()->cond; 3480 }; 3481 #ifndef NDEBUG 3482 auto get_env_dst = [&](const auto& e) 3483 { 3484 return mmw->out(e.dst).begin()->dst; 3485 }; 3486 #endif 3487 3488 // The first two loops cover all env-edges 3489 for (unsigned group = 0; group < n_groups; ++group) 3490 { 3491 const auto& min_let_g = red.minimal_letters[group]; 3492 const auto& min_let_v_g = red.minimal_letters_vec[group]; 3493 const unsigned nmlg = min_let_v_g.size(); 3494 3495 for (unsigned src = 0; src < n_env; ++src) 3496 { 3497 if (red.which_group[src] != group) 3498 continue; 3499 for (const auto& e : mmw->out(src)) 3500 // Check which minimal letters implies this edge 3501 { 3502 // All minimal words of this group 3503 for (unsigned abddidu = 0; abddidu < nmlg; ++abddidu) 3504 { 3505 const auto& impl_sets = 3506 min_let_g.at(min_let_v_g[abddidu]); 3507 if (impl_sets.first.count(e.cond.id())) 3508 { 3509 bdd outcond = get_o_cond(e); 3510 // This edge has the "letter" abddidu 3511 // abddidu -> e.cond 3512 // Loop over all possible src- and dst-classes 3513 // AND the out conditions 3514 for (unsigned src_class = 0; 3515 src_class < n_classes; 3516 ++src_class) 3517 { 3518 if (!x_in_class[src_class].second[e.src]) 3519 continue; 3520 for (unsigned dst_class = 0; 3521 dst_class < n_classes; 3522 ++dst_class) 3523 { 3524 // Currently we only use the first one 3525 // but we still loop over 3526 // all if changed later 3527 auto it = used_ziaj_map.find({src_class, 3528 abddidu, 3529 dst_class}); 3530 if (it != used_ziaj_map.end()) 3531 { 3532 assert( 3533 x_in_class[dst_class] 3534 .second[get_env_dst(e)]); 3535 it->second &= outcond; 3536 } 3537 } // dst_class 3538 } // src_class 3539 } 3540 } // min_let 3541 } // e 3542 } // s 3543 } // groups 3544 // Check if all the outconds are actually feasible, 3545 // that is all outconds are not false 3546 for (const auto& el : used_ziaj_map) 3547 if (el.second == bddfalse) 3548 infeasible_classes.emplace_back(el.first.i, el.first.a); 3549 if (!infeasible_classes.empty()) 3550 { 3551 // Remove the variable clauses 3552 // This is suboptimal but the contexts form a stack so... 3553 dotimeprint << "Refining constraints for " 3554 << infeasible_classes.size() << " classses.\n"; 3555 mm_pb.unset_variable_clauses(); 3556 add_bdd_cond_constr(mm_pb, mmw, red, n_env, 3557 infeasible_classes, x_in_class); 3558 continue; //retry 3559 } 3560 3561 cstr_split_mealy(minmach, red, x_in_class, used_ziaj_map); 3562 3563 // todo: What is the impact of chosing one of the possibilities 3564 minmach->set_init_state(init_class_v.front()); 3565 return minmach; 3566 } // while loop 3567 } // try_build_machine 3568 } // namespace 3569 3570 namespace spot 3571 { minimize_mealy(const const_twa_graph_ptr & mm,int premin)3572 twa_graph_ptr minimize_mealy(const const_twa_graph_ptr& mm, 3573 int premin) 3574 { 3575 assert(is_split_mealy(mm)); 3576 3577 stopwatch sw; 3578 sw.start(); 3579 3580 if ((premin < -1) || (premin > 1)) 3581 throw std::runtime_error("premin has to be -1, 0 or 1"); 3582 3583 auto orig_spref = get_state_players(mm); 3584 3585 // Check if finite traces exist 3586 // If so, deactivate fast minimization 3587 // todo : this is overly conservative 3588 // If unreachable states have no outgoing edges we do not care 3589 // but testing this as well starts to be expensive... 3590 if (premin != -1 3591 && [&]() 3592 { 3593 for (unsigned s = 0; s < mm->num_states(); ++s) 3594 { 3595 auto eit = mm->out(s); 3596 if (eit.begin() == eit.end()) 3597 return true; 3598 } 3599 return false; 3600 }()) 3601 premin = -1; 3602 3603 auto do_premin = [&]()->const_twa_graph_ptr 3604 { 3605 if (premin == -1) 3606 return mm; 3607 else 3608 { 3609 // We have a split machine -> unsplit then resplit, 3610 // as reduce mealy works on separated 3611 auto mms = unsplit_mealy(mm); 3612 reduce_mealy_here(mms, premin == 1); 3613 split_separated_mealy_here(mms); 3614 return mms; 3615 } 3616 }; 3617 3618 const_twa_graph_ptr mmw = do_premin(); 3619 assert(is_split_mealy(mmw)); 3620 dotimeprint << "Done premin " << sw.stop() << '\n'; 3621 3622 // 0 -> "Env" next is input props 3623 // 1 -> "Player" next is output prop 3624 const auto& spref = get_state_players(mmw); 3625 assert((spref.size() == mmw->num_states()) 3626 && "Inconsistent state players"); 3627 3628 // Reorganize the machine such that 3629 // first block: env-states 3630 // second black : player-states 3631 unsigned n_env = -1u; 3632 std::tie(mmw, n_env) = reorganize_mm(mmw, spref); 3633 assert(is_split_mealy(mmw)); 3634 #ifdef TRACE 3635 print_hoa(std::cerr, mmw); 3636 #endif 3637 assert(n_env != -1u); 3638 dotimeprint << "Done reorganise " << n_env << " - " 3639 << sw.stop() << '\n'; 3640 3641 // Compute incompatibility based on bdd 3642 auto incompmat = compute_incomp(mmw, n_env, sw); 3643 dotimeprint << "Done incompatibility " << sw.stop() << '\n'; 3644 #ifdef TRACE 3645 incompmat.print(std::cerr); 3646 #endif 3647 3648 // Get a partial solution 3649 auto partsol = get_part_sol(incompmat); 3650 dotimeprint << "Done partial solution " << partsol.psol.size() 3651 << " - " << sw.stop() << '\n'; 3652 3653 3654 auto early_exit = [&]() 3655 { 3656 // Always keep machines split 3657 assert(is_split_mealy_specialization(mm, mmw)); 3658 return std::const_pointer_cast<twa_graph>(mmw); 3659 }; 3660 3661 // If the partial solution has the same number of 3662 // states as the original automaton -> we are done 3663 if (partsol.psol.size() == n_env) 3664 { 3665 dotimeprint << "Done trans comp " << 1 << " - " << sw.stop() << '\n'; 3666 dotimeprint << "Done comp all letters " << " - " 3667 << sw.stop() << '\n'; 3668 #ifdef MINTIMINGS 3669 dotimeprint << "Done comp all min sim letters 0 - " 3670 << sw.stop() << '\n'; 3671 #endif 3672 dotimeprint << "Done splitting " << sw.stop() << '\n'; 3673 dotimeprint << "Done split and reduce " << sw.stop() << '\n'; 3674 dotimeprint << "Done build init prob " << sw.stop() << '\n'; 3675 dotimeprint << "Done minimizing - " << mmw->num_states() 3676 << " - " << sw.stop() << '\n'; 3677 return early_exit(); 3678 } 3679 3680 // Get the reduced alphabet 3681 auto [split_mmw, reduced_alphabet] = 3682 reduce_and_split(mmw, n_env, incompmat, sw); 3683 dotimeprint << "Done split and reduce " << sw.stop() << '\n'; 3684 3685 auto mm_pb = build_init_prob<true>(split_mmw, incompmat, 3686 reduced_alphabet, partsol, n_env); 3687 dotimeprint << "Done build init prob " << sw.stop() << '\n'; 3688 3689 twa_graph_ptr minmachine = nullptr; 3690 for (size_t n_classes = partsol.psol.size(); 3691 n_classes < n_env; ++n_classes) 3692 { 3693 minmachine = try_build_min_machine(mm_pb, mmw, 3694 reduced_alphabet, 3695 partsol, n_env, 3696 sw); 3697 dotimeprint << "Done try_build " << n_classes 3698 << " - " << sw.stop() << '\n'; 3699 3700 if (minmachine) 3701 break; 3702 increment_classes(split_mmw, incompmat, reduced_alphabet, 3703 partsol, mm_pb); 3704 dotimeprint << "Done incrementing " << sw.stop() << '\n'; 3705 } 3706 // Is already minimal -> Return a copy 3707 // Set state players! 3708 if (!minmachine) 3709 return early_exit(); 3710 set_synthesis_outputs(minmachine, get_synthesis_outputs(mm)); 3711 dotimeprint << "Done minimizing - " << minmachine->num_states() 3712 << " - " << sw.stop() << '\n'; 3713 3714 assert(is_split_mealy_specialization(mm, minmachine)); 3715 return minmachine; 3716 } 3717 } 3718 3719 namespace spot 3720 { is_split_mealy_specialization(const_twa_graph_ptr left,const_twa_graph_ptr right,bool verbose)3721 bool is_split_mealy_specialization(const_twa_graph_ptr left, 3722 const_twa_graph_ptr right, 3723 bool verbose) 3724 { 3725 assert(is_split_mealy(left)); 3726 assert(is_split_mealy(right)); 3727 3728 const unsigned initl = left->get_init_state_number(); 3729 const unsigned initr = right->get_init_state_number(); 3730 3731 auto& spr = get_state_players(right); 3732 #ifndef NDEBUG 3733 auto& spl = get_state_players(left); 3734 // todo 3735 auto check_out = [](const const_twa_graph_ptr& aut, 3736 const auto& sp) 3737 { 3738 for (unsigned s = 0; s < aut->num_states(); ++s) 3739 if (sp.at(s)) 3740 if (((++aut->out(s).begin()) != aut->out(s).end()) 3741 || (aut->out(s).begin() == aut->out(s).end())) 3742 { 3743 std::cerr << "Failed for " << s << '\n'; 3744 return false; 3745 } 3746 3747 return true; 3748 }; 3749 assert(check_out(left, spl) && 3750 "Left mealy machine has multiple or no player edges for a state"); 3751 assert(check_out(right, spr) && 3752 "Right mealy machine has multiple or no player edges for a state"); 3753 #endif 3754 // Get for each env state of right the uncovered input letters 3755 std::vector<bdd> ucr(right->num_states(), bddtrue); 3756 const unsigned nsr = right->num_states(); 3757 for (unsigned s = 0; s < nsr; ++s) 3758 { 3759 if (spr[s]) 3760 continue; 3761 for (const auto& e : right->out(s)) 3762 ucr[s] -= e.cond; 3763 } 3764 3765 using prod_state = std::pair<unsigned, unsigned>; 3766 3767 std::unordered_set<prod_state, pair_hash> seen; 3768 std::deque<prod_state> todo; 3769 todo.emplace_back(initl, initr); 3770 seen.emplace(todo.back()); 3771 3772 auto get_p_edge_l = [&](const auto& e_env) 3773 {return *(left->out(e_env.dst).begin()); }; 3774 auto get_p_edge_r = [&](const auto& e_env) 3775 {return *(right->out(e_env.dst).begin()); }; 3776 3777 while (!todo.empty()) 3778 { 3779 const auto [sl, sr] = todo.front(); 3780 todo.pop_front(); 3781 for (const auto& el_env : left->out(sl)) 3782 { 3783 // check if el_env.cond intersects with the unspecified of 3784 // sr. If so the sequence is not applicable -> false 3785 if (bdd_have_common_assignment(ucr[sr], el_env.cond)) 3786 { 3787 if (verbose) 3788 std::cerr << "State " << sl << " of left is not completely" 3789 << " covered by " << sr << " of right.\n"; 3790 return false; 3791 } 3792 3793 3794 const auto& el_p = get_p_edge_l(el_env); 3795 3796 for (const auto& er_env : right->out(sr)) 3797 { 3798 // if they can be taken at the same time, the output 3799 // of r must implies the one of left 3800 if (bdd_have_common_assignment(el_env.cond, er_env.cond)) 3801 { 3802 const auto& er_p = get_p_edge_r(er_env); 3803 if (!bdd_implies(er_p.cond, el_p.cond)) 3804 { 3805 if (verbose) 3806 std::cerr << "left " << el_env.src << " to " 3807 << el_env.dst << " and right " 3808 << er_env.src << " to " << er_env.dst 3809 << " have common letter " 3810 << (el_env.cond & er_env.cond) << " but " 3811 << er_p.cond << " does not imply " 3812 << el_p.cond << std::endl; 3813 return false; 3814 } 3815 3816 3817 // Check if the new dst pair was already visited 3818 assert(spl[el_p.src] && !spl[el_p.dst]); 3819 assert(spr[er_p.src] && !spr[er_p.dst]); 3820 auto [itdst, inserted] = seen.emplace(el_p.dst, 3821 er_p.dst); 3822 if (inserted) 3823 todo.push_back(*itdst); 3824 } 3825 } 3826 } 3827 } 3828 return true; 3829 } 3830 3831 } 3832