We are happy to announce the release of Spot 2.3.2.
This is a maintenance release that only contains minor bug fixes, and
minor enhancements, as listed below.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.3.2.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.3.2 (2017-03-15)
Tools:
- In tools that output automata, the number of atomic propositions
can be output using --stats=%x (output automaton) or --stats=%X
(input automaton). Additional options can be passed to list
atomic propositions instead of counting them. Tools that output
formulas also support --format=%x for this purpose.
Python:
- The bdd_to_formula(), and to_generalized_buchi() functions can now
be called in Python.
Documentation:
- https://spot.lrde.epita.fr/tut11.html is a new page describing
how to build monitors in Shell, Python, or C++.
Bugs fixed:
- The tests using LTSmin's patched version of divine would fail
if the current (non-patched) version of divine was installed.
- Because of a typo, the output of --stats='...%P...' was correct
only if %p was used as well.
- genltl was never meant to have (randomly attributed) short
options for --postive and --negative.
- a typo in the code for transformating transition-based acceptance
to state-based acceptance could cause a superfluous initial state
to be output in some cases (the result was still correct).
- 'ltl2tgba --any -C -M ...' would not complete automata.
- While not incorrect, the HOA properties output by 'ltl2tgba -M'
could be 'inherently-weak' or 'terminal', while 'ltl2tgba -M -D'
would always report 'weak' automata. Both variants now report the
most precise between 'weak' or 'terminal'.
- spot::twa_graph::set_univ_init_state() could not be called with
an initializer list.
- The Python wrappers for spot::twa_graph::state_from_number and
spot::twa_graph::state_acc_sets were broken in 2.3.
- Instantiating an emptiness check on an automaton with unsupported
acceptance condition should throw an exception. This used to be
just an assertion, disabled in release builds; the difference
matters for the Python bindings.
Deprecation notice:
- Using --format=%a to print the number of atomic propositions in
ltlfilt, genltl, and randltl still works, but it is not documented
anymore and should be replaced by the newly-introduced --format=%x
for consistency with tools producing automata, where %a means
something else.
--
Alexandre Duret-Lutz
I have subscribed Thomas Medioni to the list.
He is a master student from Paris 6 who will be working on
implementing various algorithms for generic acceptance conditions,
starting with some conversions between different acceptance
conditions.
His initial task is to implement --sum-or and --sum-and
(https://gitlab.lrde.epita.fr/spot/spot/issues/231)
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.3.1.
This is a maintenance release that only contains minor bug fixes, and
minor enhancements, as listed below.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.3.1.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
The contributors to this release are Arthur Remaud, Étienne Renault,
Maximilien Colange, Vincent Tourneur, and myself. As always, please
direct any feedback to <spot(a)lrde.epita.fr>.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.3.1 (2017-02-20)
Tools:
- ltldo learnt to act like a portfolio: --smallest and --greatest
will select the best output automaton for each formula translated.
See https://spot.lrde.epita.fr/ltldo.html#portfolio for examples.
- The colors used in the output of ltlcross have been adjusted to
work better with white backgrounds and black backgrounds.
- The option (y) has been added to --dot. It splits the universal
edges with the same targets but different colors.
- genltl learnt three new families for formulas: --kr-n2=RANGE,
--kr-nlogn=RANGE, and --kr-n=RANGE. These formulas, from
Kupferman & Rosenberg [MoChArt'10] are recognizable by
deterministic Büchi automata with at least 2^2^n states.
Library:
- spot::twa_run::as_twa() has an option to preserve state names.
- the method spot::twa::is_alternating(), introduced in Spot 2.3 was
badly named and has been deprecated. Use the negation of the new
spot::twa::is_existential() instead.
Bugs fixed:
- spot::otf_product() was incorrectly registering atomic
propositions.
- spot::ltsmin_model::kripke() forgot to register the "dead"
proposition.
- The spot::acc_word type (used to construct acceptance condition)
was using some non-standard anonymous struct. It is unlikely that
this type was actually used outside Spot, but if you do use it,
spot::acc_word::op and spot::acc_word::type had to be renamed as
spot::acc_word::sub.op and spot::acc_word::sub.type.
- alternation_removal() was not always reporting the unsupported
non-weak automata.
- a long-standing typo in the configure code checking for Python
caused any user-defined CPPFLAGS to be ignored while building
Spot.
- The display of clusters with universal edges was confused, because the
intermediate node was not in the cluster even if one of the target was
in the same one.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.3.
Spot is a library of algorithms for manipulating LTL formulas and
omega-automata (objects as commonly used in model checking).
This new release features some exiting news such as
- faster emptiness checks for automata that are not explored
on-the-fly,
- several improvements to the SAT-based minimization procedure,
- preliminary support for alternating automata,
- membership tests for all classes of the Manna and Pnueli hierarchy
of temporal properties.
See below for more details.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.3.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
The contributors to this release are Maximilien Colange, Alexandre
Gbaguidi Aisse, Étienne Renault, and myself. As always, please direct
any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.3 (2017-01-19)
Build:
* While Spot only relies on C++11 features, the configure script
learned --enable-c++14 to compile in C++14 mode. This allows us
check that nothing breaks when we will switch to C++14.
* Spot is now distributed with PicoSAT 965, and uses it for
SAT-based minimization of automata without relying on temporary
files. It is still possible to use an external SAT solver by
setting the SPOT_SATSOLVER environment variable.
* The development Debian packages for Spot now install static
libraries as well.
* We now install configuration files for users of pkg-config.
Tools:
* ltlcross supports translators that output alternating automata in
the HOA format. Cross-comparison checks will only work with weak
alternating automata (not necessarily *very* weak), but "ltlcross
--no-check --product=0 --csv=..." will work with any alternating
automaton if you just want satistics.
* autfilt can read alternating automata. This is still experimental
(see below). Some of the algorithms proposed by autfilt will
refuse to work because they have not yet been updated to work with
alternating automata, but in any case they should display a
diagnostic: if you see a crash, please report it.
* autfilt has three new filters: --is-very-weak, --is-alternating,
and --is-semi-deterministic.
* the --check option of autfilt/ltl2tgba/ltldo/dstar2tgba can now
take "semi-determinism" as argument.
* autfilt --highlight-languages will color states that recognize
identical languages. (Only works for deterministic automata.)
* 'autfilt --sat-minimize' and 'ltl2tgba -x sat-minimize' have
undergone some backward incompatible changes. They use binary
search by default, and support different options than they used
too. See spot-x(7) for details. The defaults are those that were
best for the benchmark in bench/dtgbasat/.
* ltlfilt learned --recurrence and --persistence to match formulas
belonging to these two classes of the temporal hierarchy. Unlike
--syntactic-recurrence and --syntactic-persistence, the new checks
are automata-based and will also match pathological formulas.
See https://spot.lrde.epita.fr/hierarchy.html
* The --format option of ltlfilt/genltl/randltl/ltlgrind learned to
print the class of a formula in the temporal hierarchy of Manna &
Pnueli using %h. See https://spot.lrde.epita.fr/hierarchy.html
* ltldo and ltlcross learned a --relabel option to force the
relabeling of atomic propositions to p0, p1, etc. This is more
useful with ltldo, as it allows calling a tool that restricts the
atomic propositions it supports, and the output automaton will
then be fixed to use the original atomic propositions.
* ltldo and ltlcross have learned how to call ltl3hoa, so
'ltl3hoa -f %f>%O' can be abbreviated to just 'ltl3hoa'.
Library:
* A twa is required to have at least one state, the initial state.
An automaton can only be empty while it is being constructed,
but should not be passed to other algorithms.
* Couvreur's emptiness check has been rewritten to use the explicit
interface when possible, to avoid overkill memory allocations.
The new version has further optimizations for weak and terminal
automata. Overall, this new version is roughly 4x faster on
explicit automata than the former one. The old version has been
kept for backward compatibility, but will be removed eventually.
* The new version of the Couvreur emptiness check is now the default
one, used by twa::is_empty() and twa::accepting_run(). Always
prefer these functions over an explicit call to Couvreur.
* experimental support for alternating automata:
- twa_graph objects can now represent alternating automata. Use
twa_graph::new_univ_edge() and twa_graph::set_univ_init_state()
to create universal edges an initial states; and use
twa_graph::univ_dests() to iterate over the universal
destinations of an edge.
- the automaton parser will now read alternating automata in the
HOA format. The HOA and dot printers can output them.
- the file twaalgos/alternation.hh contains a few algorithms
specific to alternating automata:
+ remove_alternation() will transform *weak* alternating automata
into TGBA.
+ the class outedge_combiner can be used to perform "and" and "or"
on the outgoing edges of some alternating automaton.
- scc_info has been adjusted to handle universal edges as if they
were existential edges. As a consequence, acceptance
information is not accurate.
- postprocessor will call remove_alternation() right away, so
it can be used as a way to transform alternating automata
into different sub-types of (generalized) Büchi automata.
Note that although prostprocessor optimize the resulting
automata, it still has no simplification algorithms that work
at the alternating automaton level.
- See https://spot.lrde.epita.fr/tut23.htmlhttps://spot.lrde.epita.fr/tut24.html and
https://spot.lrde.epita.fr/tut31.html for some code examples.
* twa objects have two new properties, very-weak and
semi-deterministic, that can be set or retrieved via
twa::prop_very_weak()/twa::prop_semi_deterministic(), and that can
be tested by is_very_weak_automaton()/is_semi_deterministic().
* twa::prop_set has a new attribute used in twa::prop_copy() and
twa::prop_keep() to indicate that determinism may be improved by
an algorithm. In other words properties like
deterministic/semi-deterministic/unambiguous should be preserved
only if they are positive.
* language_map() and highlight_languages() are new functions that
implement autfilt's --highlight-languages option mentionned above.
* dtgba_sat_minimize_dichotomy() and dwba_sat_minimize_dichotomy()
use language_map() to estimate a lower bound for binary search.
* The encoding part of SAT-based minimization consumes less memory.
* SAT-based minimization of automata can now be done using two
incremental techniques that take a solved minimization and attempt
to forbid the use of some states. This is done either by adding
clauses, or by using assumptions.
* If the environment variable "SPOT_XCNF" is set during incremental
SAT-based minimization, XCNF files suitable for the incremental SAT
competition will be generated. This requires the use of an exteral
SAT solver, setup with "SPOT_SATSOLVER". See spot-x(7).
* The new function mp_class(f) returns the class of the formula
f in the temporal hierarchy of Manna & Pnueli.
Python:
* spot.show_mp_hierarchy() can be used to display the membership of
a formula to the Manna & Pnueli hierarchy, in notebooks. An
example is in https://spot.lrde.epita.fr/ipynb/formulas.html
* The on-line translator will now display the temporal hierarchy
in the "Formula > property information" output.
Bugs fixed:
* The minimize_wdba() function was not correctly minimizing automata
with useless SCCs. This was not an issue for the LTL translation
(where useless SCCs are always removed first), but it was an issue
when deciding if a formula was safety or guarantee. As a
consequence, some tricky safety or guarantee properties were only
recognized as obligations.
* When ltlcross was running a translator taking the Spin syntax as
input (%s) it would not automatically relabel any unsupported
atomic propositions as ltldo already do.
* When running "autfilt --sat-minimize" on a automaton representing
an obligation property, the result would always be a complete
automaton even without the -C option.
* ltlcross --products=0 --csv should not output any product-related
column in the CSV output since it has nothing to display there.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.2.2.
This is a maintenance release that only contains minor bug fixes, as
listed below.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.2.2.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.2.2 (2016-12-16)
Build:
* If the system has an installed libltdl library, use it instead of
the one we distribute.
Bug fixes:
* scc_filter() had a left-over print statement that would print
"names" when copying the name of the states.
* is_terminal() should reject automata that have accepting
transitions going into rejecting SCCs. The whole point of
being a terminal automaton is that reaching an accepting
transition guarantees that any suffix will be accepted.
* The HOA parser incorrectly read "Acceptance: 1 Bar(0)" as a valid
way to specify "Acceptance: 1 Fin(0)" because it assumed that
everything that was not Inf was Fin. These errors are now
diagnosed.
* Some of the installed headers (spot/misc/fixpool.hh,
spot/misc/mspool.hh, spot/twaalgos/emptiness_stats.hh) were not
self-contained.
* ltlfilt --from-ltlf should ensure that "alive" holds initially in
order to reject empty traces.
* the on-line translator had a bug where a long ltl3ba process would
continue running even after the script had timeout'ed.
--
Alexandre Duret-Lutz
We are ashamed to announce the release of Spot 2.2.1.
This release contains only one bug fix, for a segfault that was
introduced in Spot 2.2. Many thanks to Tomáš Babiak for the report.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.2.1.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.2.1 (2016-11-21)
Bug fix:
* The bdd_noderesize() function, as modified in 2.2, would always
crash.
We are happy to announce the release of Spot 2.2.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.2.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
Spot 2.2 fixes some serious bugs and adds an assortments of small
improvements. These changes have been contributed by Alexandre
Gbaguidi Aisse, Étienne Renault, and myself. A detailed list of what
is new is given below.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.2 (2016-11-14)
Command-line tools:
* ltlfilt has a new option --from-ltlf to help reducing LTLf (i.e.,
LTL over finite words) model checking to LTL model checking. This
is based on a transformation by De Giacomo & Vardi (IJCAI'13).
* "ltldo --stats=%R", which used to display the serial number of the
formula processed, was renamed to "ltldo --stats=%#" to free %R
for the following feature.
* autfilt, dstar2tgba, ltl2tgba, ltlcross, ltldo learned to measure
cpu-time (as opposed to wall-time) using --stats=%R. User or
system time, for children or parent, can be measured separately by
adding additional %[LETTER]R options. The difference between %r
(wall-clock time) and %R (CPU time) can also be used to detect
unreliable measurements. See
https://spot.lrde.epita.fr/oaut.html#timing
Library:
* from_ltlf() is a new function implementing the --from-ltlf
transformation described above.
* is_unambiguous() was rewritten in a more efficient way.
* scc_info learned to determine the acceptance of simple SCCs made
of a single self-loop without resorting to remove_fin() for complex
acceptance conditions.
* remove_fin() has been improved to better deal with automata with
"unclean" acceptance, i.e., acceptance sets that are declared but
not used. In particular, this helps scc_info to be more efficient
at deciding the acceptance of SCCs in presence of Fin acceptance.
* Simulation-based reductions now implement just bisimulation-based
reductions on deterministic automata, to save time. As an example,
this halves the run time of
genltl --rv-counter=10 | ltl2tgba
* scc_filter() learned to preserve state names and highlighted states.
* The BuDDy library has been slightly optimized: the initial setup
of the unicity table can now be vectorized by GCC, and all calls
to setjmp are now avoided when variable reordering is disabled
(the default).
* The twa class has three new methods:
aut->intersects(other)
aut->intersecting_run(other)
aut->intersecting_word(other)
currently these are just convenient wrappers around
!otf_product(aut, other)->is_empty()
otf_product(aut, other)->accepting_run()->project(aut)
otf_product(aut, other)->accepting_word()
with any Fin-acceptance removal performed before the product.
However the plan is to implement these more efficiently in the
future.
Bugs:
* ltl2tgba was always using the highest settings for the LTL
simplifier, ignoring the --low and --medium options. Now
genltl --go-theta=12 | ltl2tgba --low --any
is instantaneous as it should be.
* The int-vector compression code could encode 6 and 22 in the
same way, causing inevitable issues in our LTSmin interface.
(This affects tests/ltsmin/modelcheck with option -z, not -Z.)
* str_sere() and str_utf8_sere() were not returning the same
string that print_sere() and print_utf8_sere() would print.
* Running the LTL parser in debug mode would crash.
* tgba_determinize() could produce incorrect deterministic automata
when run with use_simulation=true (the default) on non-simplified
automata.
* When the automaton_stream_parser reads an automaton from an
already opened file descriptor, it will not close the file
anymore. Before that the spot.automata() python function used to
close a file descriptor twice when reading from a pipe, and this
led to crashes of the 0MQ library used by Jupyter, killing the
Python kernel.
* remove_fin() could produce incorrect result on incomplete
automata tagged as weak and deterministic.
* calling set_acceptance() several times on an automaton could
result in unexpected behaviors, because set_acceptance(0,...)
used to set the state-based acceptance flag automatically.
* Some buffering issue caused syntax errors to be displayed out
of place by the on-line translator.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.1.2.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.1.2.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
Spot 2.1.2 contains a handful of bug fixes and a couple of minor
improvements, as listed below. These changes were contributed by
Étienne Renault, Alexandre Gbaguidi Aïsse, and myself.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.1.2 (2014-10-14)
Command-line tools:
* genltl learned 5 new families of formulas
(--tv-f1, --tv-f2, --tv-g1, --tv-g2, --tv-uu)
defined in Tabakov & Vardi's RV'10 paper.
* ltlcross's --csv and --json output was changed to not include
information about the ambiguity or strength of the automata by
default. Computing those can be costly and not needed by
every user, so it should now be requested explicitely using
options --strength and --ambiguous.
Library:
* New LTL simplification rule:
- GF(f & q) = G(F(f) & q) if q is
purely universal and a pure eventuality. In particular
GF(f & GF(g)) now ultimately simplifies to G(F(f) & F(g)).
Bug fixes:
* Fix spurious uninitialized read reported by valgrind when
is_Kleene_star() is compiled by clang++.
* Using "ltlfilt some-large-file --some-costly-filter" could take
to a lot of time before displaying the first results, because the
output of ltlfilt is buffered: the buffer had to fill up before
being flushed. The issue did not manifest when the input is
standard input, because of the C++ feature that reading std::cin
should flush std::cout; however it was well visible when reading
from files. Flushing is now done more regularly.
* Fix compilation warnings when -Wimplicit-fallthrough it enabled.
* Fix python errors on Darwin when using methods from the spot module
inside of the spot.ltsmin submodule.
* Fix ltlcross crash when combining --no-check with --verbose.
* Adjust paths and options used in bench/dtgbasat/ to match the
changes introduced in Spot 2.0.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.1.1.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.1.1.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
Spot 2.1.1 contains some very minor fixups, and a few command-line
improvements that should really have been part of 2.1.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.1.1 (2016-09-20)
Command-line tools:
* ltlfilt, randltl, genltl, and ltlgrind learned to display the size
(%s), Boolean size (%b), and number of atomic propositions (%a)
with the --format and --output options. A typical use-case is to
sort formulas by size:
genltl --dac --format='%s,%f' | sort -n | cut -d, -f2
or to group formulas by number of atomic propositions:
genltl --dac --output='ap-%a.ltl'
* autfilt --stats learned the missing %D, %N, %P, and %W sequences,
to complete the existing %d, %n, %p, and %w.
* The --stats %c option of ltl2tgba, autfilt, ltldo, and dstar2tgba
now accepts options to filter the SCCs to count. For instance
--stats='%[awT]c' will count the SCCs that are (a)ccepting and
(w)eak, but (not t)erminal. See --help for all supported filters.
Bugs fixed:
* Fix several cases where command-line tools would fail to diagnose
write errors (e.g. when writing to a filesystem that is full).
* Typos in genltl --help and in the man page spot-x(7).
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.1.
Spot 2.1 is mainly a collection of small improvements that have
accumulated since the release of Spot 2.0 four months ago. A
detailed list of those is given below.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.1.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.1 (2016-08-08)
Command-line tools:
* All tools that input formulas or automata (i.e., autfilt,
dstar2tgba, ltl2tgba, ltl2tgta, ltlcross, ltldo, ltlfilt,
ltlgrind) now have a more homogeneous handling of the default
input.
- If no formula/automaton have been specified, and the standard
input is a not a tty, then the default is to read that. This is a
change for ltl2tgba and ltl2tgta. In particular, it simplifies
genltl --dac | ltl2tgba -F- | autfilt ...
into
genltl --dac | ltl2tgba | autfilt ...
- If standard input is a tty and no other input has been
specified, then an error message is printed. This is a change for
autfilt, dstar2tgba, ltlcross, ltldo, ltlfilt, ltlgrind, that used
to expect the user to type formula or automata at the terminal,
confusing people.
- All tools now accept - as a shorthand for -F-, to force reading
input from the standard input (regardless of whether it is a tty
or not). This is a change for ltl2tgba, ltl2tgta, ltlcross, and
ltldo.
* ltldo has a new option --errors=... to specify how to deal
with errors from executed tools.
* ltlcross and ltldo learned to bypass the shell when executing
simple commands (with support for single or double-quoted
arguments, and redirection of stdin and stdout, but nothing more).
* ltlcross and ltldo learned a new syntax to specify that an input
formula should be written in some given syntax after rewriting
some operators away. For instance the defaults arguments passed
to ltl2dstar have been changed from
--output-format=hoa %L %O
into
--output-format=hoa %[WM]L %O
where [WM] specifies that operators W and M should be rewritten
away. As a consequence running
ltldo ltl2dstar -f 'a M b'
will now work and call ltl2dstar on the equivalent formula
'b U (a & b)' instead. The operators that can be listed between
brackets are the same as those of ltlfilt --unabbreviate option.
* ltlcross learned to show some counterexamples when diagnosing
failures of cross-comparison checks against random state spaces.
* autfilt learned to filter automata by count of SCCs (--sccs=RANGE)
or by type of SCCs (--accepting-sccs=RANGE,
--rejecting-sccs=RANGE, trivial-sccs=RANGE, --terminal-sccs=RANGE,
--weak-sccs=RANGE, --inherently-weak-sccs=RANGE).
* autfilt learned --remove-unused-ap to remove atomic propositions
that are declared in the input automaton, but not actually used.
This of course makes sense only for input/output formats that
declare atomic propositions (HOA & DSTAR).
* autfilt learned two options to filter automata by count of used or
unused atomic propositions: --used-ap=RANGE --unused-ap=RANGE.
These differ from --ap=RANGE that only consider *declared* atomic
propositions, regardless of whether they are actually used.
* autfilt learned to filter automata by count of nondeterministsic
states with --nondet-states=RANGE.
* autfilt learned to filter automata representing stutter-invariant
properties with --is-stutter-invariant.
* autfilt learned two new options to highlight non-determinism:
--highlight-nondet-states=NUM and --highlight-nondet-states=NUM
where NUM is a color number. Additionally --highlight-nondet=NUM is
a shorthand for using the two.
* autfilt learned to highlight a run matching a given word using the
--highlight-word=[NUM,]WORD option. However currently this only
work on automata with Fin-less acceptance.
* autfilt learned two options --generalized-rabin and
--generalized-streett to convert the acceptance conditions.
* genltl learned three new families: --dac-patterns=1..45,
--eh-patterns=1..12, and --sb-patterns=1..27. Unlike other options
these do not output scalable patterns, but simply a list of formulas
appearing in these three papers: Dwyer et al (FMSP'98), Etessami &
Holzmann (Concur'00), Somenzi & Bloem (CAV'00).
* genltl learned two options, --positive and --negative, to control
wether formulas should be output after negation or not (or both).
* The formater used by --format (for ltlfilt, ltlgrind, genltl,
randltl) or --stats (for autfilt, dstar2tgba, ltl2tgba, ltldo,
randaut) learned to recognize double-quoted fields and double the
double-quotes output inbetween as expected from RFC4180-compliant
CSV files. For instance
ltl2tgba -f 'a U "b+c"' --stats='"%f",%s'
will output
"a U ""b+c""",2
* The --csv-escape option of genltl, ltlfilt, ltlgrind, and randltl
is now deprecated. The option is still here, but hidden and
undocumented.
* The --stats option of autfilt, dstar2tgba, ltl2tgba, ltldo,
randaut learned to display the output (or input if that makes
sense) automaton as a HOA one-liner using %h (or %H), helping to
create CSV files contained automata.
* autfilt and dstar2tgba learned to read automata from columns in
CSV files, specified using the same filename/COLUMN syntax used by
tools reading formulas.
* Arguments passed to -x (in ltl2tgba, ltl2tgta, autfilt, dstar2tgba)
that are not used are now reported as they might be typos.
This ocurred a couple of times in our test-suite. A similar
check is done for the arguments of autfilt --sat-minimize=...
Library:
* The print_hoa() function will now output version 1.1 of the HOA
format when passed the "1.1" option (i.e., use -H1.1 from any
command-line tool). As far as Spot is concerned, this allows
negated properties to be expressed. Version 1 of the HOA format
is still the default, but we plan to default to version 1.1 in the
future.
* The "highlight-states" and "highlight-edges" named properties,
which were introduced in 1.99.8, will now be output using
"spot.highlight.edges:" and "spot.highlight.states:" headers if
version 1.1 of the HOA format is selected. The automaton parser
was secretly able of reading that since 1.99.8, but that is now
documented at https://spot.lrde.epita.fr/hoa.html#extensions
* highlight_nondet_states() and highlight_nondet_edges() are
new functions that define the above two named properties.
* is_deterministic(), is_terminal(), is_weak(), and
is_inherently_weak(), count_nondet_states(),
highlight_nondet_edges(), highlight_nondet_states() will update
the corresponding properties of the automaton as a side-effect of
their check.
* the sbacc() function, used by "ltl2tgba -S" and "autfilt -S" to
convert automata to state-based acceptance, learned some tricks
(using SCCs, pulling accepting marks common to all outgoing edges,
and pushing acceptance marks common to all incoming edges) to
reduce the number of additional states needed.
* to_generalized_rabin() and to_generalized_streett() are two new
functions that convert the acceptance condition as requested
without changing the transition structure.
* language_containment_checker now has default values for all
parameters of its constructor.
* spot::twa_run has a new method, project(), that can be used to
project a run found in a product onto one of the original operand.
This is for instance used by autfilt --highlight-word.
The old spot::project_twa_run() function has been removed: it was
not used anywhere in Spot, and had an obvious bug in its
implementation, so it cannot be missed by anyone.
* spot::twa has two new methods that supplement is_empty():
twa::accepting_run() and twa::accepting_word(). They compute
what their names suggest. Note that twa::accepting_run(), unlike
the two others, is currently restricted to automata with Fin-less
acceptance.
* spot::check_stutter_invariance() can now work on non-deterministic
automata for which no corresponding formula is known. This
implies that "autfilt --check=stutter" will now label all
automata, not just deterministic automata.
* New LTL and PSL simplification rules:
- if e is pure eventuality and g => e, then e U g = Fg
- if u is purely universal and u => g, then u R g = Gg
- {s[*0..j]}[]->b = {s[*1..j]}[]->b
- {s[*0..j]}<>->b = {s[*1..j]}<>->b
* spot::twa::succ_iterable renamed to
spot::internal::twa_succ_iterable to make it clear this is not for
public consumption.
* spot::fair_kripke::state_acceptance_conditions() renamed to
spot::fair_kripke::state_acceptance_mark() for consistency. This
is backward incompatible, but we are not aware of any actual use
of this method.
Python:
* The __format__() method for formula supports the same
operator-rewritting feature introduced in ltldo and ltlcross.
So "{:[i]s}".format(f) is the same as
"{:s}".format(f.unabbreviate("i")).
* Bindings for language_containment_checker were added.
* Bindings for randomize() were added.
* Iterating over edges via "aut.out(s)" or "aut.edges()"
now allows modifying the edge fields.
* Under IPython the spot.ltsmin module now offers a
%%pml magic to define promela models, compile them
with spins, and dynamically load them. This is
akin to the %%dve magic that was already supported.
* The %%dve and %%pml magics honor the SPOT_TMPDIR and
TMPDIR environment variables. This especially helps
when the current directory is read-only.
Documentation:
* A new example page shows how to test the equivalence of
two LTL/PSL formulas. https://spot.lrde.epita.fr/tut04.html
* A new page discusses explicit vs. on-the-fly interfaces for
exploring automata in C++. https://spot.lrde.epita.fr/tut50.html
* Another new page shows how to implement an on-the-fly Kripke
structure for a custom state space.
https://spot.lrde.epita.fr/tut51.html
* The concepts.html page now lists all named properties
used by automata.
Bug fixes:
* When ltlcross found a bug using a product of complemented
automata, the error message would report "Comp(Ni)*Comp(Pj)" as
non-empty while the actual culprit was "Comp(Nj)*Comp(Pi)".
* Fix some non-deterministic execution of minimize_wdba(), causing
test-suite failures with the future G++ 7, and clang 3.9.
* print_lbtt() had a memory leak when printing states without
successors.
--
Alexandre Duret-Lutz
