twasafracomplement.hh 3.07 KB
Newer Older
1
// -*- coding: utf-8 -*-
2
3
// Copyright (C) 2009, 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
#pragma once
21

22
#include <vector>
23
#include <spot/twa/twa.hh>
24

25
26
27
28
29
#ifndef TRANSFORM_TO_TBA
# define TRANSFORM_TO_TBA 0
#endif
#define TRANSFORM_TO_TGBA (!TRANSFORM_TO_TBA)

30
31
namespace spot
{
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
32
  /// \ingroup twa_on_the_fly_algorithms
33
  /// \brief Build a complemented automaton.
34
35
36
37
38
39
40
41
42
  ///
  /// It creates an automaton that recognizes the
  /// negated language of \a aut.
  ///
  /// 1. First Safra construction algorithm produces a
  ///    deterministic Rabin automaton.
  /// 2. Interpreting this deterministic Rabin automaton as a
  ///    deterministic Streett will produce a complemented automaton.
  /// 3. Then we use a transformation from deterministic Streett
43
  ///    automaton to nondeterministic Büchi automaton.
44
45
46
47
  ///
  ///  Safra construction is done in \a tgba_complement, the transformation
  ///  is done on-the-fly when successors are called.
  ///
48
  /// \sa safra_determinisation, tgba_safra_complement::succ_iter.
49
  class SPOT_API tgba_safra_complement : public twa
50
51
  {
  public:
52
    tgba_safra_complement(const const_twa_graph_ptr& a);
53
    virtual ~tgba_safra_complement();
54
55
56

    // tgba interface.
    virtual state* get_init_state() const;
57
    virtual twa_succ_iterator* succ_iter(const state* state) const;
58
59
60

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

61
62
63
64
65
    void* get_safra() const
    {
      return safra_;
    }

66
67
68
  protected:
    virtual bdd compute_support_conditions(const state* state) const;
  private:
69
    const_twa_graph_ptr automaton_;
70
    void* safra_;
71
#if TRANSFORM_TO_TBA
72
    acc_cond::mark_t the_acceptance_cond_;
73
74
75
#endif
#if TRANSFORM_TO_TGBA
    // Map to i the i-th acceptance condition of the final automaton.
76
    std::vector<acc_cond::mark_t> acceptance_cond_vec_;
77
#endif
78
79
  };

80
81
82
83
  typedef std::shared_ptr<tgba_safra_complement> tgba_safra_complement_ptr;
  typedef std::shared_ptr<const tgba_safra_complement>
    const_tgba_safra_complement_ptr;
  inline tgba_safra_complement_ptr
84
  make_safra_complement(const const_twa_graph_ptr& a)
85
86
87
88
  {
    return std::make_shared<tgba_safra_complement>(a);
  }

89
90
91
  /// \brief Produce a dot output of the Safra automaton associated
  /// to \a a.
  ///
92
  /// \param a The \c tgba_safra_complement with an intermediate Safra
93
  /// automaton to display
94
  void SPOT_API display_safra(const const_tgba_safra_complement_ptr& a);
95
}