We are happy to announce the release of Spot 2.4.2
This is a maintenance release containing only minor bug fixes and
documentation changes.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.4.2.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
New in spot 2.4.2 (2017-11-07)
Tools:
- ltlcross and ltldo support ltl3tela, the new name of ltl3hoa.
Bugs fixed:
- Automata produced by "genaut --ks-nca=N" were incorrectly marked
as not complete.
- Fix some cases for which the highest setting of formulas
simplification would produce worse results than lower settings.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.4.1
This is a maintenance release containing only bug fixes.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.4.1.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
This release contains patches contributed by Maximilien Colange,
Florian Perlié-Long, Alexandre Gbaguidi Aïsse, and myself.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.4.1 (2017-10-05)
Bugs fixed:
- The formula class failed to build {a->c[*]} although it is
allowed by our grammar.
- spot::scc_info::determine_unknown_acceptance() incorrectly
considered some rejecting SCC as accepting.
- spot::streett_to_generalized_buchi() could generate automata with
empty language if some Fin set did not intersect all accepting
SCCs. As a consequence, some Streett-like automata were
considered empty even though they were not. Also, the same
function could crash on input that had a Streett-like acceptance
not using all declared sets.
- The twa_graph::merge_edges() function relied on BDD IDs to sort
edges. This in turn caused some algorithms (like the
degeneralization) to produce slighltly different (but still correct)
outputs depending on the BDD operations performed before.
- spot::simulation() could incorrectly flag an automaton as
non-deterministic.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.4.
Spot is a library of algorithms for manipulating LTL formulas and
omega-automata (objects as commonly used in model checking).
A detailed list of new features in this new release is given at the end
of this email. You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.4.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
This release contains code contributed by Clément Gillard, Etienne
Renault, Henrich Lauko, Maximilien Colange, Thomas Medioni and myself.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.4 (2017-09-06)
Build:
- Spot is now built in C++14 mode, so you need at least GCC 5 or
clang 3.4. The current version of all major linux distributions
ship with at least GCC 6, which defaults to C++14, so this should
not be a problem. In *this* release of Spot, most of the header
files are still C++11 compatible, so you should be able to include
Spot in a C++11 project in case you do not yet want to upgrade.
There is also an --enable-c++17 option to configure in case you
want to force a build of Spot in C++17 mode.
Tools:
- genaut is a new binary that produces families of automata defined
in the literature (in the same way as we have genltl for LTL
formulas).
- autcross is a new binary that compares the output of tools
transforming automata (in the same way as we have ltlcross for
LTL translators).
- genltl learned two generate two new families of formulas:
--fxg-or=RANGE F(p0 | XG(p1 | XG(p2 | ... XG(pn))))
--gxf-and=RANGE G(p0 & XF(p1 & XF(p2 & ... XF(pn))))
The later is a generalization of --eh-pattern=9, for which a
single state TGBA always exists (but previous version of Spot
would build larger automata).
- autfilt learned to build the union (--sum) or the intersection
(--sum-and) of two languages by putting two automata side-by-side
and fiddling with the initial states. This complements the already
implemented intersection (--product) and union (--product-or),
both based on a product.
- autfilt learned to complement any alternating automaton with
option --dualize. (See spot::dualize() below.)
- autfilt learned --split-edges to convert labels that are Boolean
formulas into labels that are min-terms. (See spot::split_edges()
below.)
- autfilt learned --simplify-acceptance to simplify some acceptance
conditions. (See spot::simplify_acceptance() below.)
- autfilt --decompote-strength has been renamed to --decompose-scc
because it can now extract the subautomaton leading to an SCC
specified by number. (The old name is still kept as an alias.)
- The --stats=%c option of tools producing automata can now be
restricted to count complete SCCs, using %[c]c.
- Tools producing automata have a --stats=... option, and tools
producing formulas have a --format=... option. These two options
work similarly, the use of different names is just historical.
Starting with this release, all tools that recognize one of these
two options also accept the other one as an alias.
Library:
- A new library, libspotgen, gathers all functions used to generate
families of automata or LTL formulas, used by genltl and genaut.
- spot::sum() and spot::sum_and() implements the union and the
intersection of two automata by putting them side-by-side and
using non-deterministim or universal branching on the initial
state.
- twa objects have a new property: prop_complete(). This obviously
acts as a cache for the is_complete() function.
- spot::dualize() complements any alternating automaton. Since
the dual of a deterministic automaton is still deterministic, the
function spot::dtwa_complement() has been deprecated and simply
calls spot::dualize().
- spot::decompose_strength() was extended and renamed to
spot::decompose_scc() as it can now also extract a subautomaton
leading to a particular SCC. A demonstration of this feature via
the Python bindings can be found at
https://spot.lrde.epita.fr/ipynb/decompose.html
- The print_dot() function will now display names for well known
acceptance conditions under the formula when option 'a' is used.
We plan to enable 'a' by default in a future release, so a new
option 'A' has been added to hide the acceptance condition.
- The print_dot() function has a new experimental option 'x' to
output labels are LaTeX formulas. This is meant to be used in
conjunction with the dot2tex tool. See
https://spot.lrde.epita.fr/oaut.html#dot2tex
- A new named property for automata called "original-states" can be
used to record the origin of a state before transformation. It is
currently defined by the degeneralization algorithms, and by
transform_accessible() and algorithms based on it (like
remove_ap::strip(), decompose_scc()). This is realy meant as an
aid for writing algorithms that need this mapping, but it can also
be used to debug these algorithms: the "original-states"
information is displayed by the dot printer when the 'd' option is
passed. For instance in
% ltl2tgba 'GF(a <-> Fb)' --dot=s
% ltl2tgba 'GF(a <-> Fb)' | autfilt -B --dot=ds
the second command outputs an automaton with states that show
references to the first one.
- A new named property for automata called "degen-levels" keeps track
of the level of a state in a degeneralization. This information
complements the one carried in "original-states".
- A new named property for automata called "simulated-states" can be
used to record the origin of a state through simulation. The
behavior is similar to "original-states" above. Determinization
takes advantage of this in its pretty print.
- The new function spot::acc_cond::is_streett_like() checks whether
an acceptance condition is conjunction of disjunctive clauses
containing at most one Inf and at most one Fin. It builds a
vector of pairs to use if we want to assume the automaton has
Streett acceptance. The dual function is
spot::acc_cond::is_rabin_like() works similarly.
- The degeneralize() function has learned to consider acceptance
marks common to all edges comming to a state to select its initial
level. A similar trick was already used in sbacc(), and saves a
few states in some cases.
- There is a new spot::split_edges() function that transforms edges
(labeled by Boolean formulas over atomic propositions) into
transitions (labeled by conjunctions where each atomic proposition
appear either positive or negative). This can be used to
preprocess automata before feeding them to algorithms or tools
that expect transitions labeled by letters.
- spot::scc_info has two new methods to easily iterate over the
edges of an SCC: edges_of() and inner_edges_of().
- spot::scc_info can now be passed a filter function to ignore
or cut some edges.
- spot::scc_info now keeps track of acceptance sets that are common
to all edges in an SCC. These can be retrieved using
scc_info::common_sets_of(scc), and they are used by scc_info to
classify some SCCs as rejecting more easily.
- The new function acc_code::remove() removes all the given
acceptance sets from the acceptance condition.
- It is now possible to change an automaton acceptance condition
directly by calling twa::set_acceptance().
- spot::cleanup_acceptance_here now takes an additional boolean
parameter specifying whether to strip useless marks from the
automaton. This parameter is defaulted to true, in order to
keep this modification backward-compatible.
- The new function spot::simplify_acceptance() is able to perform
some simplifications on an acceptance condition, and might lead
to the removal of some acceptance sets.
- The function spot::streett_to_generalized_buchi() is now able to
work on automata with Streett-like acceptance.
- The function for converting deterministic Rabin automata to
deterministic Büchi automata (when possible), internal to the
remove_fin() procedure, has been updated to work with
transition-based acceptance and with Rabin-like acceptance.
- spot::relabel_here() was used on automata to rename atomic
propositions, it can now replace atomic propositions by Boolean
subformula. This makes it possible to use relabeling maps
produced by relabel_bse() on formulas.
- twa_graph::copy_state_names_from() can be used to copy the state
names from another automaton, honoring "original-states" if
present.
- Building automata for LTL formula with a large number N of atomic
propositions can be costly, because several loops and
data-structures are exponential in N. However a formula like
((a & b & c) | (d & e & f)) U ((d & e & f) | (g & h & i))
can be translated more efficiently by first building an automaton
for (p0 | p1) U (p1 | p2), and then substituting p0, p1, p2 by the
appropriate Boolean formula. Such a trick is now attempted
for translation of formulas with 4 atomic propositions or
more (this threshold can be changed, see -x relabel-bool=N in
the spot-x(7) man page).
- The LTL simplification routines learned that an LTL formula like
G(a & XF(b & XFc & Fd) can be simplified to G(a & Fb & Fc & Fd),
and dually F(a | XG(b | XGc | Gd)) = F(a | Gb | Gc | Gd).
When working with SERE, the simplification of "expr[*0..1]" was
improved. E.g. {{a[*]|b}[*0..1]} becomes {a[*]|b} instead of
{{a[+]|b}[*0..1]}.
- The new function spot::to_weak_alternating() is able to take an
input automaton with generalized Büchi/co-Büchi acceptance and
convert it to a weak alternating automaton.
- spot::sbacc() is can now also convert alternating automata
to state-based acceptance.
- spot::sbacc() and spot::degeneralize() learned to merge
accepting sinks.
- If the SPOT_BDD_TRACE environment variable is set, statistics
about BDD garbage collection and table resizing are shown.
- The & and | operators for acceptannce conditions have been changed
slightly to be more symmetrical. In older versions, operator &
would move Fin() terms to the front, but that is not the case
anymore. Also operator & was already grouping all Inf() terms
(for efficiency reasons), in this version operator | is
symmetrically grouping all Fin() terms.
- The automaton parser is now reentrant, making it possible to
process automata from different streams at the same time (i.e.,
using multiple spot::automaton_stream_parser instances at once).
- The print_hoa() and parse_automaton() functions have been updated
to recognize the "exist-branch" property of the non-released HOA
v1.1, as well as the new meaning of property "deterministic". (In
HOA v1 "properties: deterministic" means that the automaton has no
existential branching; in HOA v1.1 it disallows universal
branching as well.) The meaning of "deterministic" in Spot has
been adjusted to these new semantics, see "Backward-incompatible
changes" below.
- The parser for HOA now recognizes and verifies correct use of the
"univ-branch" property. This is known to be a problem with option
-H1 of ltl3ba 1.1.2 and ltl3dra 0.2.4, so the environment variable
SPOT_HOA_TOLERANT can be set to disable the diagnostic.
Python:
- The 'spot.gen' package exports the functions from libspotgen.
See https://spot.lrde.epita.fr/ipynb/gen.html for examples.
Bugs fixed:
- When the remove_fin() function was called on some automaton with
Inf-less acceptance involving at least one disjunction (e.g.,
generalized co-Büchi), it would sometimes output an automaton with
transition-based acceptance but marked as state-based.
- The complete() function could complete an empty co-Büchi automaton
into an automaton accepting everything.
Backward-incompatible changes:
- spot::acc_cond::mark_t::operator bool() has been marked as
explicit. The implicit converion to bool (and, via bool, to int)
was a source of bugs.
- spot::twa_graph::set_init_state(const state*) has been removed.
It was never used. You always want to use
spot::twa_graph::set_init_state(unsigned) in practice.
- The previous implementation of spot::is_deterministic() has been
renamed to spot::is_universal(). The new version of
spot::is_deterministic() requires the automaton to be both
universal and existential. This should not make any difference in
existing code unless you work with the recently added support for
alternating automata.
- spot::acc_cond::mark_t::sets() now returns an internal iterable
object instead of an std::vector<unsigned>.
- The color palette optionally used by print_dot() has been extended
from 9 to 16 colors. While the first 8 colors are similar, they
are a bit more saturated now.
Deprecation notices:
(These functions still work but compilers emit warnings.)
- spot::decompose_strength() is deprecated, it has been renamed
to spot::decompose_scc().
- spot::dtwa_complement() is deprecated. Prefer the more generic
spot::dualize() instead.
- The spot::twa::prop_deterministic() methods have been renamed to
spot::twa::prop_universal() for consistency with the change to
is_deterministic() listed above. We have kept
spot::twa::prop_deterministic() as a deprecated synonym for
spot::twa::prop_universal() to help backward compatibility.
- The spot::copy() function is deprecated. Use
spot::make_twa_graph() instead.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.3.5
This is a maintenance release containing only bug fixes.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.3.5.tar.gz
See https://spot.lrde.epita.fr/ for documentation and installation
instructions.
Furthermore, as Debian 9 "Stretch" was recently released, the stable
Debian packages we distribute (see
http://www.lrde.epita.fr/install.html) are now built for Stretch.
As always, please direct any feedback to <spot(a)lrde.epita.fr>.
New in spot 2.3.5 (2017-06-22)
Bugs fixed:
- We have fixed new cases where translating multiple formulas in a
single ltl2tgba run could produce automata different from those
produced by individual runs.
- The print_dot() function had a couple of issues when printing
alternating automata: in particular, when using flag 's' (display
SCC) or 'y' (split universal destination by colors) universal
edges could be connected to undefined states.
- Using --stats=%s or --stats=%s or --stats=%t could take an
unnecessary long time on automata with many atomic propositions,
due to a typo. Furthermore, %s/%e/%t/%E/%T were printing
a number of reachable states/edges/transitions, but %S was
incorrectly counting all states even unreachable.
- Our verson of BuDDy had an incorrect optimization for the
biimp operator.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.3.4
This is a maintenance release that only contains bug fixes
(listed below), and also corrects some minor build issues and
typos.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.3.4.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.4 (2017-05-11)
Bugs fixed:
- The transformation to state-based acceptance (spot::sbacc()) was
incorrect on automata where the empty acceptance mark is accepting.
- The --help output of randaut and ltl2tgba was showing an
unsupported %b stat.
- ltldo and ltlcross could leave temporary files behind when
aborting on error.
- The LTL simplifcation rule that turns F(f)|q into F(f|q)
when q is a subformula that is both eventual and universal
was documented but not applied in some forgotten cases.
- Because of some caching inside of ltl2tgba, translating multiple
formula in single ltl2tgba run could produce automata different
from those produced by individual runs.
--
Alexandre Duret-Lutz
We are happy to announce the release of Spot 2.3.3.
This is a maintenance release that only contains minor bug fixes, and
minor enhancements, as listed below. This release contains
contributions from Thomas Medioni, Maximilien Colange, and myself.
You can find the new release here:
http://www.lrde.epita.fr/dload/spot/spot-2.3.3.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.3 (2017-04-11)
Tools:
- ltldo and ltlcross learned shorthands to talk to ltl2da, ltl2dpa,
and ltl2ldba (from Owl) without needing to specify %f>%O.
- genltl learned --spec-patterns as an alias for --dac-patterns; it
also learned two new sets of LTL formulas under --hkrss-patterns
(a.k.a. --liberouter-patterns) and --p-patterns
(a.k.a. --beem-patterns).
Bugs fixed:
- In "lenient" mode the formula parser would fail to recover from a
missing closing brace.
- The output of 'genltl --r-left=1 --r-right=1 --format=%F' had
typos.
- 'ltl2tgba Fa | autfilt --complement' would incorrectly claim that
the output is "terminal" because dtwa_complement() failed to reset
that property.
- spot::twa_graph::purge_unreachable_states() was misbehaving on
alternating automata.
- In bench/stutter/ the .cc files were not compiling due to warnings
being caught as errors.
- The code in charge of detecting DBA-type Rabin automata is
actually written to handle a slightly larger class of acceptance
conditions (e.g., Fin(0)|(Fin(1)&Inf(2))), however it failed to
correctly detect DBA-typeness in some of these non-Rabin
acceptance.
--
Alexandre Duret-Lutz
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
