simplify.hh 6.51 KB
Newer Older
1
2
// Copyright (C) 2011, 2012, 2013 Laboratoire de Recherche et
// Developpement de l'Epita (LRDE).
3
4
5
6
7
//
// 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
8
// the Free Software Foundation; either version 3 of the License, or
9
10
11
12
13
14
15
16
// (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
17
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
18
19
20
21
22
23

#ifndef SPOT_LTLVISIT_SIMPLIFY_HH
# define SPOT_LTLVISIT_SIMPLIFY_HH

#include "ltlast/formula.hh"
#include "bdd.h"
24
#include "tgba/bdddict.hh"
25
#include <iosfwd>
26
27
28
29
30
31
32
33

namespace spot
{
  namespace ltl
  {
    class ltl_simplifier_options
    {
    public:
34
35
36
37
38
      ltl_simplifier_options(bool basics = true,
			     bool synt_impl = true,
			     bool event_univ = true,
			     bool containment_checks = false,
			     bool containment_checks_stronger = false,
39
			     bool nenoform_stop_on_boolean = false,
40
			     bool reduce_size_strictly = false,
41
42
			     bool boolean_to_isop = false,
			     bool favor_event_univ = false)
43
44
45
46
47
	: reduce_basics(basics),
	  synt_impl(synt_impl),
	  event_univ(event_univ),
	  containment_checks(containment_checks),
	  containment_checks_stronger(containment_checks_stronger),
48
	  nenoform_stop_on_boolean(nenoform_stop_on_boolean),
49
	  reduce_size_strictly(reduce_size_strictly),
50
51
	  boolean_to_isop(boolean_to_isop),
	  favor_event_univ(favor_event_univ)
52
53
54
55
56
57
58
59
      {
      }

      bool reduce_basics;
      bool synt_impl;
      bool event_univ;
      bool containment_checks;
      bool containment_checks_stronger;
60
61
      // If true, Boolean subformulae will not be put into
      // negative normal form.
62
      bool nenoform_stop_on_boolean;
63
64
65
66
      // If true, some rules that produce slightly larger formulae
      // will be disabled.  Those larger formulae are normally easier
      // to translate, so we recommend to set this to false.
      bool reduce_size_strictly;
67
68
      // If true, Boolean subformulae will be rewritten in ISOP form.
      bool boolean_to_isop;
69
70
      // Try to isolate subformulae that are eventual and universal.
      bool favor_event_univ;
71
72
73
74
75
76
    };

    // fwd declaration to hide technical details.
    class ltl_simplifier_cache;

    /// \ingroup ltl_rewriting
77
    /// \brief Rewrite or simplify \a f in various ways.
78
    class SPOT_API ltl_simplifier
79
80
    {
    public:
81
      ltl_simplifier(bdd_dict* dict = 0);
82
      ltl_simplifier(const ltl_simplifier_options& opt, bdd_dict* dict = 0);
83
84
      ~ltl_simplifier();

85
86
      /// Simplify the formula \a f (using options supplied to the
      /// constructor).
87
      const formula* simplify(const formula* f);
88
89
90

      /// Build the negative normal form of formula \a f.
      /// All negations of the formula are pushed in front of the
91
92
      /// atomic propositions.  Operators <=>, =>, xor are all removed
      /// (calling spot::ltl::unabbreviate_ltl is not needed).
93
94
95
96
      ///
      /// \param f The formula to normalize.
      /// \param negated If \c true, return the negative normal form of
      ///        \c !f
97
98
      const formula*
      negative_normal_form(const formula* f, bool negated = false);
99

100
101
102
103
104
      /// \brief Syntactic implication.
      ///
      /// Returns whether \a f syntactically implies \a g.
      ///
      /// This is adapted from
105
106
107
108
109
110
111
112
113
114
115
116
117
      /** \verbatim
          @InProceedings{          somenzi.00.cav,
          author         = {Fabio Somenzi and Roderick Bloem},
          title          = {Efficient {B\"u}chi Automata for {LTL} Formulae},
          booktitle      = {Proceedings of the 12th International Conference on
                           Computer Aided Verification (CAV'00)},
          pages          = {247--263},
          year           = {2000},
          volume         = {1855},
          series         = {Lecture Notes in Computer Science},
          publisher      = {Springer-Verlag}
          }
          \endverbatim */
118
119
120
121
122
123
      ///
      bool syntactic_implication(const formula* f, const formula* g);
      /// \brief Syntactic implication with one negated argument.
      ///
      /// If \a right is true, this method returns whether
      /// \a f implies !\a g.  If \a right is false, this returns
124
      /// whether !\a f implies \a g.
125
126
127
128
129
130
131
132
133
      bool syntactic_implication_neg(const formula* f, const formula* g,
				     bool right);

      /// \brief check whether two formulae are equivalent.
      ///
      /// This costly check performs up to four translations,
      /// two products, and two emptiness checks.
      bool are_equivalent(const formula* f, const formula* g);

134
135
136
137
138
139
140
141

      /// \brief Check whether \a f implies \a g.
      ///
      /// This operation is costlier than syntactic_implication()
      /// because it requires two translation, one product and one
      /// emptiness check.
      bool implication(const formula* f, const formula* g);

142
143
144
145
146
147
      /// \brief Convert a Boolean formula as a BDD.
      ///
      /// If you plan to use this method, be sure to pass a bdd_dict
      /// to the constructor.
      bdd as_bdd(const formula* f);

148
149
150
151
152
153
154
      /// \brief Clear the as_bdd() cache.
      ///
      /// Calling this function is recommended before running other
      /// algorithms that create BDD variables in a more natural
      /// order.  For instance ltl_to_tgba_fm() will usually be more
      /// efficient if the BDD variables for atomic propositions have
      /// not been ordered before hand.
155
156
      ///
      /// This also clears the language containment cache.
157
158
      void clear_as_bdd_cache();

159
160
      /// Return the bdd_dict used.
      bdd_dict* get_dict() const;
161

162
163
164
      /// Cached version of spot::ltl::star_normal_form().
      const formula* star_normal_form(const formula* f);

165
166
167
168
169
170
171
      /// \brief Rewrite a Boolean formula \a f into as an irredundant
      /// sum of product.
      ///
      /// This uses a cache, so it is OK to call this with identical
      /// arguments.
      const formula* boolean_to_isop(const formula* f);

172
173
174
      /// Dump statistics about the caches.
      void print_stats(std::ostream& os) const;

175
176
    private:
      ltl_simplifier_cache* cache_;
177
      // Copy disallowed.
178
179
180
      ltl_simplifier(const ltl_simplifier&) = delete;
      void operator=(const ltl_simplifier&) = delete;

181
      bool owndict;
182
183
184
185
186
187
    };
  }

}

#endif // SPOT_LTLVISIT_SIMPLIFY_HH