sabacomplementtgba.hh 2.58 KB
Newer Older
1
// Copyright (C) 2009, 2010, 2013, 2014 Laboratoire de Recherche et Développement
Guillaume Sadegh's avatar
Guillaume Sadegh committed
2
// 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
24
25
26
27
28

#ifndef SPOT_SABA_SABACOMPLEMENTTGBA_HH
#define SPOT_SABA_SABACOMPLEMENTTGBA_HH

#include <tgba/tgba.hh>
#include <tgba/tgbatba.hh>
#include "saba.hh"

namespace spot
{
  /// \ingroup saba
29
  /// \brief Complement a TGBA and produce a SABA.
30
31
  ///
  /// The original TGBA is transformed into a States-based
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
32
  /// Büchi Automaton.
33
34
35
36
37
38
  ///
  /// Several techniques are supposed to by applied on the resulting
  /// automaton before its transformation into a TGBA.  Those techniques
  /// are expected to reduce the size of the automaton.
  ///
  /// This algorithm comes from:
39
40
41
42
43
44
45
46
47
48
49
  /** \verbatim
      @Article{         gurumurthy.03.lncs,
        title         = {On complementing nondeterministic {B\"uchi} automata},
        author        = {Gurumurthy, S. and Kupferman, O. and Somenzi, F. and
                        Vardi, M.Y.},
        journal       = {Lecture Notes in Computer Science},
        pages         = {96--110},
        year          = {2003},
        publisher     = {Springer-Verlag}
      }
      \endverbatim */
50
51
52
53
  ///
  /// The construction is done on-the-fly, by the
  /// \c saba_complement_succ_iterator class.
  /// \see saba_complement_succ_iterator
54
  class SPOT_API saba_complement_tgba : public saba
55
56
57
58
59
60
61
62
63
64
65
66
67
68
  {
  public:
    saba_complement_tgba(const tgba* a);
    virtual ~saba_complement_tgba();

    // tgba interface
    virtual saba_state* get_init_state() const;
    virtual saba_succ_iterator*
    succ_iter(const saba_state* local_state) const;

    virtual bdd_dict* get_dict() const;
    virtual std::string format_state(const saba_state* state) const;
    virtual bdd all_acceptance_conditions() const;
  private:
69
    const tgba_digraph* automaton_;
70
71
72
73
74
75
76
77
    bdd the_acceptance_cond_;
    unsigned nb_states_;
  }; // end class tgba_saba_complement.

} // end namespace spot.


#endif  // SPOT_SABA_SABACOMPLEMENTTGBA_HH