tgbatba.hh 4.36 KB
Newer Older
1
2
// Copyright (C) 2010 Laboratoire de Recherche et Développement de
// l'Epita.
3
4
5
// Copyright (C) 2003, 2004, 2006 Laboratoire d'Informatique de Paris
// 6 (LIP6), département Systèmes Répartis Coopératifs (SRC),
// Université Pierre et Marie Curie.
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//
// 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
// the Free Software Foundation; either version 2 of the License, or
// (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
// along with Spot; see the file COPYING.  If not, write to the Free
// Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
// 02111-1307, USA.

24
25
26
#ifndef SPOT_TGBA_TGBATBA_HH
# define SPOT_TGBA_TGBATBA_HH

27
#include <list>
28
29
30
31
32
33
#include "tgba.hh"
#include "misc/bddlt.hh"

namespace spot
{

34
  /// \brief Degeneralize a spot::tgba on the fly, producing a TBA.
35
  /// \ingroup tgba_on_the_fly_algorithms
36
37
  ///
  /// This class acts as a proxy in front of a spot::tgba, that should
38
39
40
  /// be degeneralized on the fly.  The result is still a spot::tgba,
  /// but it will always have exactly one acceptance condition so
  /// it could be called TBA (without the G).
41
42
43
44
45
46
  ///
  /// The degeneralization is done by synchronizing the input
  /// automaton with a "counter" automaton such as the one shown in
  /// "On-the-fly Verification of Linear Temporal Logic" (Jean-Michel
  /// Couveur, FME99).
  ///
47
  /// If the input automaton uses N acceptance conditions, the output
48
  /// automaton can have at most max(N,1) times more states and
49
  /// transitions.
50
51
  ///
  /// \see tgba_sba_proxy
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
  class tgba_tba_proxy : public tgba
  {
  public:
    tgba_tba_proxy(const tgba* a);

    virtual ~tgba_tba_proxy();

    virtual state* get_init_state() const;

    virtual tgba_succ_iterator*
    succ_iter(const state* local_state,
	      const state* global_state = 0,
	      const tgba* global_automaton = 0) const;

    virtual bdd_dict* get_dict() const;

    virtual std::string format_state(const state* state) const;

70
    virtual state* project_state(const state* s, const tgba* t) const;
71
72
73

    virtual std::string
    transition_annotation(const tgba_succ_iterator* t) const;
74

75
76
    virtual bdd all_acceptance_conditions() const;
    virtual bdd neg_acceptance_conditions() const;
77

78
    typedef std::list<bdd> cycle_list;
79
80
81
82
  protected:
    virtual bdd compute_support_conditions(const state* state) const;
    virtual bdd compute_support_variables(const state* state) const;

83
    cycle_list acc_cycle_;
84
    const tgba* a_;
85
  private:
86
    bdd the_acceptance_cond_;
87
88
    // Disallow copy.
    tgba_tba_proxy(const tgba_tba_proxy&);
89
    tgba_tba_proxy& operator=(const tgba_tba_proxy&);
90
91
  };

92
  /// \brief Degeneralize a spot::tgba on the fly, producing an SBA.
93
  /// \ingroup tgba_on_the_fly_algorithms
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
  ///
  /// This class acts as a proxy in front of a spot::tgba, that should
  /// be degeneralized on the fly.
  ///
  /// This is similar to tgba_tba_proxy, except that automata produced
  /// with this algorithms can also been see as State-based Büchi
  /// Automata (SBA).  See tgba_sba_proxy::state_is_accepting().  (An
  /// SBA is a TBA, and a TBA is a TGBA.)
  ///
  /// This extra property has a small cost in size: if the input
  /// automaton uses N acceptance conditions, the output automaton can
  /// have at most max(N,1)+1 times more states and transitions.
  /// (This is only max(N,1) for tgba_tba_proxy.)
  class tgba_sba_proxy : public tgba_tba_proxy
  {
  public:
    tgba_sba_proxy(const tgba* a);

    /// \brief Whether the state is accepting.
    ///
    /// A particularity of a spot::tgba_sba_proxy automaton is that
    /// when a state has an outgoing accepting arc, all its outgoing
    /// arcs are accepting.  The state itself can therefore be
    /// considered accepting.  This is useful in algorithms working on
    /// degeneralized automata with state acceptance conditions.
    bool state_is_accepting(const state* state) const;
120
121
122
123

    virtual state* get_init_state() const;
  protected:
    cycle_list::iterator cycle_start_;
124
125
  };

126
127
}
#endif // SPOT_TGBA_TGBATBA_HH