Introducing the new game interface
to ltlsynt.
ltlsynt now also uses direct strategy deduction
and formula decomposition.
* bin/ltlsynt.cc: Here
* spot/twaalgos/aiger.cc
, spot/twaalgos/aiger.hh: Use strategy_like
* spot/twaalgos/game.hh: Minor adaption
* spot/twaalgos/mealy_machine.cc: Use new interface
* spot/twaalgos/synthesis.cc
, spot/twaalgos/synthesis.hh: Spezialised split
* tests/core/ltlsynt.test
, tests/python/games.ipynb: Adapting
Also remove self-loop for sink and make it work for any
acceptance condition.
* spot/twaalgos/synthesis.cc: Here
* tests/core/ltlsynt.test: Adjust tests
* tests/python/split.py: Adjust tests
Split a LTL formula to a set of formula that don't share
output proposition. It allows to create multiple
strategies in ltlsynt.
* spot/twaalgos/synthesis.cc,
spot/twaalgos/synthesis.hh: here
* doc/spot.bib: Add reference
Introduce a new, uniform way to create and solve
games.
Games can now be created directly from specification
using creat_game, uniformly solved using
solve_game and transformed into a strategy
using create_strategy.
Strategy are mealy machines, which can be minimized.
* bin/ltlsynt.cc: Minor adaption
* spot/twaalgos/game.cc: solve_game, setters and getters
for named properties
* spot/twaalgos/game.hh: Here too
* spot/twaalgos/mealy_machine.cc: Minor adaption
* spot/twaalgos/synthesis.cc: create_game, create_strategy and
minimize_strategy
* spot/twaalgos/synthesis.hh: Here too
* tests/core/ltlsynt.test: Adapting
* tests/python/aiger.py
, tests/python/games.ipynb
, tests/python/mealy.py
, tests/python/parity.py
, tests/python/split.py: Adapting
The merging is (possibly) more expensive but also
merges more states when applied to all states.
* spot/graph/graph.hh: edge sorting
* spot/twa/twagraph.cc,
spot/twa/twagraph.hh: selective state merging
* tests/core/twagraph.cc: Adjusting tests
Aiger circuits noew have their own class.
Monitors can be translated to and obtained
from aiger circuits.
Moreover a step by step evaluation method
is provided.
* spot/twaalgos/aiger.hh,
spot/twaalgos/aiger.cc: Here
* bin/ltlsynt.cc: Adopt new modes
* tests/core/ltlsynt.test: Adapt tests
* python/spot/impl.i: Add python support
* tests/Makefile.am,
tests/python/aiger.py: New test cases
The only difference with upstream is that we keep std::malloc() as
malloc() to avoid issues with gnulib that sometimes redefine malloc to
rpl_malloc with a macro without defining std::rpl_malloc.
* spot/priv/robin_hood.hh, debian/copyright: Update.
* spot/priv/Makefile.am (update): Rename std::malloc to malloc.
* spot/parseaut/scanaut.ll: One or two digits numbers can be safely
converted to integer without risking overflow, so do that without
calling strtoul(). This simple change halves the number of calls
to strtoul() on the example automaton of issue #476.
This improves the parsing performance a bit more.
* spot/parseaut/parsedecl.hh, spot/parseaut/parseaut.yy: Here.
* tests/sanity/style.test: Handle parsedecl.hh as a private header.
On a debug build with the automaton from #476, the gain seems to be
about 33% of the parsing time.
* spot/parseaut/parseaut.yy, spot/parseaut/parsedecl.hh,
spot/parseaut/scanaut.ll: Share a hash map of string->BDD
between the scanner and parser so that [labels] can be looked
up by the scanner if they have already been parsed once.
* NEWS: Mention it.
This version of the generic emptiness-check, using smart selection and
extraction of the Fin (implemented here via fin_one_extract), was
suggested by Jan Strejček on 2020-06-26.
* spot/twaalgos/genem.cc, spot/twaalgos/genem.hh: Add the spot210
variant. Also use it for the ACD use-case.
* spot/twaalgos/zlktree.cc (zielonka_tree): Also use the same logic
here.
* tests/python/genem.py: Test the new version as well.
* spot/twa/acc.cc, spot/twa/acc.hh (acc_cond::fin_one_extract,
acc_code::acc_cond::fin_one_extract): New methods.
* python/spot/impl.i: Add support for the return type.
* tests/python/acc_cond.ipynb: Test them.
On the example from previous patch, the number of instruction fetches
goes from 18490399159 down to 18248898077.
* spot/twaalgos/zlktree.cc, spot/twaalgos/zlktree.hh (acd): Use
bitvect instead of std::vector<bool> in nodes. This make is easier to
update an edge of a bitvector shared by multiple nodes set after
pruning non-maximal sets from an SCC. Also compute the set of states
hit by the edges at the very end, once all nodes are known.
* spot/twaalgos/sccinfo.cc, spot/twaalgos/sccinfo.hh,
spot/twaalgos/genem.cc, spot/twaalgos/genem.hh: Adjust to work with
bitvect as filter.
This uses the foreach_set_index() method introduced in the previous
patch to speed up the copy bitvectors in ACD nodes, as pointed in
issue #476.
Running
PREFIXCMD='valgrind --tool=callgrind' ./run python3 -c \
"import spot; spot.acd_transform(spot.automaton('syntcomp_91.hoa'))"
went from 65139436227 instruction fetches down to 18490399159.
* spot/twaalgos/zlktree.cc (acd::build_): Use foreach_set_index().
Reported by Florian.
* spot/twaalgos/zlktree.cc: Handle the case where the condition does
not cover all colors.
* tests/python/zlktree.py: New file.
* tests/Makefile.am: Add it.
Reported by Florian Renkin.
* spot/twaalgos/zlktree.cc (acd::_build): Use a sorted list to remove
redundant children, has done in zielonka_tree.
* tests/python/zlktree.ipynb: Add Florian's test case.
* tests/python/toparity.py: Adjust, and revert some tests
uncommented by mistake in a previous patch.
This will be handy latter to develop widgets with interactive
highlighting of automata.
* spot/twaalgos/dot.cc: Implement it.
* bin/common_aoutput.cc, NEWS, doc/org/oaut.org,
doc/org/spot.css: Document it.
* tests/core/alternating.test, tests/core/readsave.test,
tests/core/sccdot.test: Test it.
* spot/twaalgos/zlktree.cc (zielonka_tree): Find the models using a
recursive procedure on the acceptance condition, without conversion to
BDD.
* tests/python/_zlktree.ipynb: Adjust to a different order of nodes.
Improve the memory usage of the acd class by sharing state-vectors and
edges-vectors.
* spot/twaalgos/zlktree.cc, spot/twaalgos/zlktree.hh: Share the
vectors during the construction, and adjust the dot output to take
this into account.
A quick and dirty implementation of the Alternating Cycle
Decomposition of the casares.21.icalp paper.
* spot/twaalgos/genem.cc, spot/twaalgos/genem.hh
(maximal_accepting_loops_for_scc): New function.
* spot/twaalgos/sccinfo.cc,
spot/twaalgos/sccinfo.hh (scc_and_mark_filter): Add a possibility to
specify a mask of transition to filter.
* spot/twaalgos/zlktree.hh, spot/twaalgos/zlktree.cc (acd): New class.
(acd_transform): New function.
* python/spot/__init__.py: Add SVG rendering for acd.
* tests/python/_zlktree.ipynb: Play with acd and acd_transform.
* tests/python/toparity.py: Add more tests to compare the
sizes of acd_transform and to_parity.
* NEWS: Mention this new feature.
* spot/twaalgos/zlktree.hh,
spot/twaalgos/zlktree.cc (zielonka_tree_transform): New function.
* tests/python/_zlktree.ipynb: Test it on three examples.
Fixes#471, reported by Cambridge Yang.
* spot/twa/twa.cc (intersecting_run): Disable the product
optimization for weak automata.
* tests/python/471.py: New file.
* tests/Makefile.am: Add it.
* NEWS: Mention the bug.
Part of #471.
* spot/twaalgos/emptiness.cc: Throw an exception if
the cycle is rejecting.
* spot/twaalgos/emptiness.hh: Document this behavior.
* tests/python/except.py: Test it.
This fixes#469.
* spot/misc/bitset.hh (bitset::operator-): Rewrite.
I cannot follow the logic of the old implementation.
* tests/python/setacc.py: Add a test case, inspired from #469.
This fixes#462.
* spot/twaalgos/gfguarantee.cc (do_g_f_terminal_inplace): Replace the
redirect_src vector by a unique_ptr<unsigned[]>. Not only does this
remove the false positive diagnostic, but it also removes the unneeded
default initialization of the elements of that vector.
