ltlgrind.org 3.67 KB
Newer Older
1
# -*- coding: utf-8 -*-
2
#+TITLE: =ltlgrind=
3
#+DESCRIPTION: Spot command-line tool for mutating LTL formulas.
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
4
#+INCLUDE: setup.org
5
#+HTML_LINK_UP: tools.html
6
#+PROPERTY: header-args:sh :results verbatim :exports both
7

8
9
10
11
12
:results scalar: Is the same as :results verbatim.

:results table: Interprets the results as an Org This tool lists
formulas that are similar to but simpler than a given formula by
applying simple mutations to it, like removing operands or
13
14
15
16
operators. This is meant to be used with ltlcross to simplify a
formula that caused a problem before trying to debug it (see also
=ltlcross --grind=FILENAME=).

17
Here is a list of the different kinds of mutations that can be applied:
18

19
20
#+BEGIN_SRC sh :exports results
ltlgrind --help | sed -n '/Mutation rules.*:/,/^$/p' | sed '1d;$d'
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#+END_SRC

#+RESULTS:
#+begin_example
      --ap-to-const          atomic propositions are replaced with true/false
      --remove-multop-operands   remove one operand from multops
      --remove-one-ap        all occurrences of an atomic proposition are
                             replaced with another atomic proposition used in
                             the formula
      --remove-ops           replace unary/binary operators with one of their
                             operands
      --rewrite-ops          rewrite operators that have a semantically simpler
                             form: a U b becomes a W b, etc.
      --simplify-bounds      on a bounded unary operator, decrement one of the
35
                             bounds, or set min to 0 or max to unbounded
36
37
38
39
40
41
42
43
44
45
46
      --split-ops            when an operator can be expressed as a
                             conjunction/disjunction using simpler operators,
                             each term of the conjunction/disjunction is a
                             mutation. e.g. a <-> b can be written as ((a & b)
                             | (!a & !b)) or as ((a -> b) & (b -> a)) so those
                             four terms can be a mutation of a <-> b
#+end_example

By default, all rules are applied. But if one or more rules are
specified, only those will be applied.

47
#+BEGIN_SRC sh
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
ltlgrind -f 'a U G(b <-> c)' --split-ops --rewrite-ops --remove-ops
#+END_SRC

#+RESULTS:
#+begin_example
a
G(b <-> c)
a W G(b <-> c)
a U (b <-> c)
a U Gb
a U Gc
a U G(b -> c)
a U G(c -> b)
a U G(b & c)
a U G(!b & !c)
#+end_example

The idea behind this tool is that when a bogus algorithm is found with
=ltlcross=, you probably want to debug it using a smaller formula than
the one found by =ltlcross=. So you would give the formula found by
=ltlcross= as an argument to =ltlgrind= and then use the resulting
mutations as an new input for =ltlcross=. It might report an error on
one of the mutation, which is guaranteed to be simpler than the
initial formula. The process can then be repeated until no error is
reported by =ltlcross=.

Since the whole process can become quite tedious, it can be done
automatically by calling =ltlcross= with the =--grind=FILENAME=
argument.

* Miscellaneous options
** =--sort=
80
  Output formulas from the shortest to the longest one. The
81
  length of a formula is the number of atomic propositions, constants
82
  and operators occurring in the formula.
83
** =-m N=, =--mutations=N=
84
85
86
87
88
89
90
91
92
  Specify the number of mutations to be applied to the formula. By
  default, =N=1=, so using this option is like calling ltlgrind on its
  own output several times, except for the fact that, when called on
  several formulas, ltlgrind doesn't handle duplicates.
** =-n N=, =--max-output=N=
   Limit the number of mutated formulas output to =N=.

#  LocalWords:  ltlgrind num toc html ltlcross FILENAME SRC sed ap Gb
#  LocalWords:  const multop multops unary decrement disjunction Gc