ltl2tgta.org 4.45 KB
Newer Older
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
1
# -*- coding: utf-8 -*-
2
#+TITLE: =ltl2tgta=
3
#+DESCRIPTION: Spot command-line tool for translating LTL into Transition-based Generalized Testing Automata.
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 code
7
8
9
10
11

This tool generates various form of Testing Automata, i.e., automata
that observe the /changes/ of atomic propositions, not their values.

Three types of automata can be output.  The only output format
12
supported currently is [[http://www.graphviz.org/][GraphViz]]'s format, with option =-8= to enable
13
14
15
16
17
18
19
20
UTF-8 characters as in other tools.

The =--ta= option will translate a formula into Testing Automaton, as
described by [[http://spinroot.com/spin/Workshops/ws06/039.pdf][Geldenhuys and Hansen (Spin'06)]].

Here is the output on =a U Gb= (we omit the call to =dot=, as shown while
discussing [[file:ltl2tgba.org][=ltl2tgba=]]).

21
#+NAME: augb-ta
22
#+BEGIN_SRC sh
23
24
ltl2tgta --ta --multiple-init 'a U Gb'
#+END_SRC
25

26
#+BEGIN_SRC dot :file augb-ta.svg :var txt=augb-ta :exports results
27
28
29
$txt
#+END_SRC
#+RESULTS:
30
[[file:augb-ta.svg]]
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

As always, the labels of the states have no influence on the language
recognized by the automaton.  This automaton has three possible
initial states.  The initial state should be chosen depending on the
initial valuation of =a= and =b= in the system to be synchronized with
this testing automaton.  For instance if =a= is true and =b= false in
the initial state, the testing automaton should start in the state
pointed to by the initial arrow labeled =a & !b=.  In the rest of the
testing automaton, the transitions are labeled by the sets of atomic
propositions that should change in the system for the testing
automaton to progress.  States with a double enclosure are Büchi
accepting, meaning that any execution that visits one of these states
is accepting.  All states have an implicit self-loop labeled by ={}=:
if the system progress without changing the value of =a= and =b=, the
testing automaton remains in the same state.  Rectangle states are
livelock-accepting: any execution of the system that get stuck into
one of these state is accepting.

Without the =--multiple-init= option, a fake initial state is added.
This is the default since it often makes the result more readable.

52
#+NAME: augb-ta2
53
#+BEGIN_SRC sh
54
55
56
ltl2tgta --ta 'a U Gb'
#+END_SRC

57
#+BEGIN_SRC dot :file augb-ta2.svg :var txt=augb-ta2 :exports results
58
59
60
$txt
#+END_SRC
#+RESULTS:
61
[[file:augb-ta2.svg]]
62
63
64
65

The =--gba= option can be used to request a Generalized Testing
Automaton, i.e., a Testing Automaton with Generalized Büchi
acceptance.  In that case double-enclosures are not used anymore, and
66
Büchi accepting transitions are marked with the same ={0,1}=
67
68
notation used in TGBA.

69
#+NAME: gfagfb-gta
70
#+BEGIN_SRC sh
71
72
73
ltl2tgta --gta 'GFa & GFb'
#+END_SRC

74
#+BEGIN_SRC dot :file gfagfb-gta.svg :var txt=gfagfb-gta :exports results
75
76
77
$txt
#+END_SRC
#+RESULTS:
78
[[file:gfagfb-gta.svg]]
79
80
81

The interpretation is similar to that of the TA.  Execution that
stutter in a livelock-accepting (square) state are accepting as well
82
as execution that visit the =0= and =1= acceptance sets
83
84
85
86
87
88
89
90
infinitely often.  Those acceptance sets are carried by transitions,
as in TGBAs.

Finally, the default is to output a Transition-based Generalized
Testing Automaton [fn:topnoc].  In TGTAs, the stuttering states are
made explicit with ={}= self-loops.  Since these self-loop can be in
acceptance sets, livelock acceptance states are no longer needed.

91
#+NAME: gfagfb-tgta
92
#+BEGIN_SRC sh
93
94
95
ltl2tgta 'GFa & GFb'
#+END_SRC

96
#+BEGIN_SRC dot :file gfagfb-tgta.svg :var txt=gfagfb-tgta :exports results
97
98
99
$txt
#+END_SRC
#+RESULTS:
100
[[file:gfagfb-tgta.svg]]
101
102


103
104
105
106
107
108
[fn:topnoc]: This new class of automata, as well as the implementation
of the previous testing automata classes, is part of Ala Eddine BEN
SALEM's PhD work, and is discussed in [[https://www.lrde.epita.fr/~adl/dl/adl/bensalem.12.topnoc.pdf][*Model checking using
generalized testing automata*]], /Ala Eddine Ben Salem/, /Alexandre
Duret-Lutz/, and /Fabrice Kordon/, in Transactions on Petri Nets and
Other Models of Concurrency (ToPNoC VI), LNCS 7400, p. 94--112, 2012.
109
110
111
112
113
114


#  LocalWords:  ltl tgta num toc Automata automata GraphViz UTF Gb na
#  LocalWords:  Geldenhuys tgba SRC init invis nb Acc augb sed png fn
#  LocalWords:  cmdline Tpng txt Büchi livelock gba gta GFa GFb TGTAs
#  LocalWords:  gfagfb topnoc Eddine SALEM's ToPNoC LNCS eval setenv
115
116
#  LocalWords:  concat getenv setq utf html args svg TGBAs Alexandre
#  LocalWords:  Duret Lutz Fabrice Kordon Petri