tgbatba.hh 4.14 KB
Newer Older
1
// -*- coding: utf-8 -*-
2
3
// Copyright (C) 2010, 2011, 2012, 2013, 2014 Laboratoire de Recherche
// et Développement de l'Epita.
4
// Copyright (C) 2003, 2004, 2006 Laboratoire d'Informatique de Paris
5
6
// 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
7
8
9
10
11
//
// 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
12
// the Free Software Foundation; either version 3 of the License, or
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
13
14
15
16
17
18
19
20
// (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
21
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
22

23
24
25
#ifndef SPOT_TGBA_TGBATBA_HH
# define SPOT_TGBA_TGBATBA_HH

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

namespace spot
{

34
  /// \ingroup tgba_on_the_fly_algorithms
35
  /// \brief Degeneralize a spot::tgba on the fly, producing a TBA.
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
  class SPOT_API tgba_tba_proxy : public tgba
51
52
53
54
55
56
57
58
  {
  public:
    tgba_tba_proxy(const tgba* a);

    virtual ~tgba_tba_proxy();

    virtual state* get_init_state() const;

59
    virtual tgba_succ_iterator* succ_iter(const state* state) const;
60
61
62
63
64

    virtual bdd_dict* get_dict() const;

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

65
    virtual state* project_state(const state* s, const tgba* t) const;
66

67
68
    virtual bdd all_acceptance_conditions() const;
    virtual bdd neg_acceptance_conditions() const;
69

70
    typedef std::list<bdd> cycle_list;
71
72
73
74
75
76
77
78
79
80
81
82
83


    /// \brief Return the acceptance conditions common to all outgoing
    /// transitions of state \a ostate in the original automaton.
    ///
    /// This internal function is only meant to be used to implement
    /// the iterator returned by succ_iter.
    ///
    /// The result of this function is computed the first time, and
    /// then cached.
    bdd common_acceptance_conditions_of_original_state(const state*
						       ostate) const;

84
85
86
87
88
89
90
91
92
93
    /// \brief Return the union of acceptance conditions of all outgoing
    /// transitions of state \a ostate in the original automaton.
    ///
    /// This internal function is only meant to be used to implement
    /// the iterator returned by succ_iter.
    ///
    /// The result of this function is computed the first time, and
    /// then cached.
    bdd union_acceptance_conditions_of_original_state(const state* s) const;

94
95
96
97
98
99
    /// \brief Create a degeneralized state using the unicity table.
    ///
    /// This is an internal function.  \a s should be a fresh state
    /// from the source automaton.
    state* create_state(state* s, cycle_list::const_iterator acc) const;

100
101
102
  protected:
    virtual bdd compute_support_conditions(const state* state) const;

103
    cycle_list acc_cycle_;
104
    const tgba* a_;
105

106
  private:
107
    bdd the_acceptance_cond_;
108
109
    typedef std::unordered_map<const state*, bdd,
			       state_ptr_hash, state_ptr_equal> accmap_t;
110
    mutable accmap_t accmap_;
111
    mutable accmap_t accmapu_;
112

113
114
115
    /// Unicity table for degeneralized states.  See create_state()
    mutable void* uniq_map_;

116
    // Disallow copy.
117
118
    tgba_tba_proxy(const tgba_tba_proxy&) SPOT_DELETED;
    tgba_tba_proxy& operator=(const tgba_tba_proxy&) SPOT_DELETED;
119
120
121
122
  };

}
#endif // SPOT_TGBA_TGBATBA_HH