tgbasafracomplement.hh 3.08 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 23
#include <vector>
#include "tgba.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
{
32
  /// \ingroup tgba_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_tgba_digraph_ptr& a);
53
    virtual ~tgba_safra_complement();
54 55 56

    // tgba interface.
    virtual state* get_init_state() const;
57
    virtual tgba_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_tgba_digraph_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_tgba_digraph_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
}