safety.cc 2.31 KB
Newer Older
1
// -*- coding: utf-8 -*-
2
3
// Copyright (C) 2010, 2011, 2013, 2014, 2015 Laboratoire de Recherche
// et Développement de l'Epita (LRDE)
4
5
6
7
8
//
// This file is part of Spot, a model checking library.
//
// Spot is free software; you can redistribute it and/or modify it
// 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
11
12
13
14
15
16
17
// (at your option) any later version.
//
// Spot is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
// or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
// License for more details.
//
// 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 "safety.hh"
21
22
#include "misc/hash.hh"
#include <deque>
23
24
25
26

namespace spot
{
  bool
27
  is_guarantee_automaton(const const_tgba_digraph_ptr& aut,
28
			 const scc_info* si)
29
  {
30
31
32
33
    if (aut->acc().uses_fin_acceptance())
      throw std::runtime_error
	("is_guarantee_automaton() does not support Fin acceptance");

34
    // Create an scc_info if the user did not give one to us.
35
36
37
    bool need_si = !si;
    if (need_si)
      si = new scc_info(aut);
38
39
40

    bool result = true;

41
    for (auto& scc: *si)
42
      {
43
	if (scc.is_rejecting())
44
	  continue;
45
46
47
48
	// Non-rejecting SCCs should necessarily be accepting, because
	// with only one self loop, there should be no ambiguity.
	if (!scc.is_accepting())
	  return false;
49
	// Accepting SCCs should have only one state.
50
	auto& st = scc.states();
51
52
53
54
55
56
57
	if (st.size() != 1)
	  {
	    result = false;
	    break;
	  }
	// The state should have only one transition that is a
	// self-loop labelled by true.
58
59
60
61
62
63
64
65
	auto src = st.front();
	auto out = aut->out(src);
	auto it = out.begin();
	assert(it != out.end());
	result =
	  (it->cond == bddtrue) && (it->dst == src) && (++it == out.end());
	if (!result)
	  break;
66
67
      }

68
69
    if (need_si)
      delete si;
70
71
72
    return result;
  }

73
  bool is_safety_mwdba(const const_tgba_digraph_ptr& aut)
74
  {
75
76
77
78
    if (!(aut->acc().is_buchi() || aut->acc().is_true()))
      throw std::runtime_error
	("is_safety_mwdba() should be called on a Buchi automaton");

79
    for (auto& t: aut->transitions())
80
81
      if (!aut->acc().accepting(t.acc))
	return false;
82
    return true;
83
  }
84
85
86
87



}