remove_x.cc 3.35 KB
Newer Older
1
// Copyright (C) 2013, 2014 Laboratoire de Recherche et Developpement de
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// l'Epita (LRDE).
//
// 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 3 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 this program.  If not, see <http://www.gnu.org/licenses/>.

#include "ltlast/allnodes.hh"
#include "ltlvisit/simplify.hh"
#include "ltlvisit/clone.hh"
#include "ltlvisit/apcollect.hh"
23
#include "ltlvisit/remove_x.hh"
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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
120
121

namespace spot
{
  namespace ltl
  {
    namespace
    {

#define AND(x, y) multop::instance(multop::And, (x), (y))
#define OR(x, y)  multop::instance(multop::Or, (x), (y))
#define NOT(x)    unop::instance(unop::Not, (x))
#define G(x)      unop::instance(unop::G, (x))
#define U(x, y)   binop::instance(binop::U, (x), (y))

      class remove_x_visitor : public clone_visitor
      {
	typedef clone_visitor super;
	atomic_prop_set aps;

      public:
	remove_x_visitor(const formula* f)
	{
	  atomic_prop_collect(f, &aps);
	}

	virtual
	~remove_x_visitor()
	{
	}

	using super::visit;
	void visit(const unop* uo)
	{
	  const formula* c = recurse(uo->child());

	  unop::type op = uo->op();
	  if (op != unop::X)
	    {
	      result_ = unop::instance(op, c);
	      return;
	    }
	  multop::vec* vo = new multop::vec;
	  for (atomic_prop_set::const_iterator i = aps.begin();
	       i != aps.end(); ++i)
	    {
	      // First line
	      multop::vec* va1 = new multop::vec;
	      const formula* npi = NOT((*i)->clone());
	      va1->push_back((*i)->clone());
	      va1->push_back(U((*i)->clone(), AND(npi, c->clone())));
	      for (atomic_prop_set::const_iterator j = aps.begin();
		   j != aps.end(); ++j)
		if (*j != *i)
		  va1->push_back(OR(U((*j)->clone(), npi->clone()),
				    U(NOT((*j)->clone()), npi->clone())));
	      vo->push_back(multop::instance(multop::And, va1));
	      // Second line
	      multop::vec* va2 = new multop::vec;
	      va2->push_back(npi->clone());
	      va2->push_back(U(npi->clone(), AND((*i)->clone(), c->clone())));
	      for (atomic_prop_set::const_iterator j = aps.begin();
		   j != aps.end(); ++j)
		if (*j != *i)
		  va2->push_back(OR(U((*j)->clone(), (*i)->clone()),
				    U(NOT((*j)->clone()), (*i)->clone())));
	      vo->push_back(multop::instance(multop::And, va2));
	    }
	  const formula* l12 = multop::instance(multop::Or, vo);
	  // Third line
	  multop::vec* va3 = new multop::vec;
	  for (atomic_prop_set::const_iterator i = aps.begin();
	       i != aps.end(); ++i)
	    {
	      va3->push_back(OR(G((*i)->clone()),
				G(NOT((*i)->clone()))));
	    }
	  result_ = OR(l12, AND(multop::instance(multop::And, va3), c));
	  return;
	}

	virtual const formula* recurse(const formula* f)
	{
	  if (f->is_X_free())
	    return f->clone();
	  f->accept(*this);
	  return this->result();
	}
      };

    }

    const formula* remove_x(const formula* f)
    {
      remove_x_visitor v(f);
      return v.recurse(f);
    }
  }
}