1. 10 Dec, 2020 1 commit
    • Alexandre Duret-Lutz's avatar
      game: rewrite, document, and rename solve_reachability_game · 9a17f567
      Alexandre Duret-Lutz authored
      * spot/twaalgos/game.hh, spot/twaalgos/game.cc: Rename
      solve_reachability_game() as solve_safety_game(), rewrite it (the old
      implementation incorrectly marked dead states as winning for their
      owner).
      * tests/python/paritygame.ipynb: Rename as...
      * tests/python/games.ipynb: ... this, and illustrate
      solve_safety_game().
      * tests/Makefile.am, NEWS, doc/org/tut.org: Adjust.
      * tests/python/except.py: Add more tests.
      9a17f567
  2. 09 Dec, 2020 2 commits
  3. 24 Sep, 2020 3 commits
    • Philipp Schlehuber's avatar
      Improving split and reorganizing · 29055c81
      Philipp Schlehuber authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * spot/twaalgos/synthesis.cc, spot/twaalgos/synthesis.hh: New files
      regrouping the functionnalities split and apply_strategy for synthesis
      * python/spot/impl.i, spot/twaalgos/Makefile.am: Add them.
      * spot/twaalgos/split.cc, spot/twaalgos/split.hh: No longer contains
      the splits necessary for for synthesis, moved to
      spot/twaalgos/synthesis.cc, spot/twaalgos/split.hh Split is now faster
      and reduces the number of intermediate states, reducing the overall
      size of the arena
      * spot/misc/game.cc, spot/misc/game.hh: Renaming propagate_players to
      alternate_players.
      * tests/core/ltlsynt.test, tests/python/split.py: Update tests.
      * bin/ltlsynt.cc: Adjust to new split. Swap order of split and
      to_parity for lar.
      29055c81
    • Alexandre Duret-Lutz's avatar
      game: let highlight_strategy work for non-parity games · 324b0872
      Alexandre Duret-Lutz authored
      This is required by an upcoming patch by Jérôme, solving reachability
      games.
      
      * spot/misc/game.cc (highlight_strategy): Do not require parity
      acceptance.
      324b0872
    • Alexandre Duret-Lutz's avatar
      game: fix handling of useless SCCs · 392c1a0e
      Alexandre Duret-Lutz authored
      This is a bug I introduced while merging Philipp's patch.
      
      * spot/misc/game.cc (parity_game::solve): Set the strategy for player
      0 in useless SCCs.
      (parity_game::fix_scc): Do not use sub_game_ to detect edges exiting
      the SCC.
      * tests/python/game.py: New file.
      * tests/Makefile.am: Add it.
      392c1a0e
  4. 22 Sep, 2020 1 commit
    • Philipp Schlehuber's avatar
      game: reimplement parity game solving · 133896d5
      Philipp Schlehuber authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * spot/misc/game.cc, spot/misc/game.hh: More efficient implementation
      of Zielonka's algorithm to solve parity games.  Now supports SCC
      decomposition and efficient handling of certain special cases.
      * doc/org/concepts.org: Document "strategy" and "state-winner"
      properties.
      * bin/ltlsynt.cc, tests/python/paritygame.ipynb: Adjust.
      * tests/core/ltlsynt.test: Add more tests.
      133896d5
  5. 16 Sep, 2020 1 commit
  6. 09 Sep, 2020 1 commit
    • Alexandre Duret-Lutz's avatar
      python: add some parity-game bindings · 760bde09
      Alexandre Duret-Lutz authored
      * python/spot/impl.i: Process game.hh.
      * spot/misc/game.cc, spot/misc/game.hh: Make the output of
      parity_game_solve() a solved_game object for easier manipulation in
      Python.
      * bin/ltlsynt.cc: Adjust usage.
      * tests/python/paritygame.ipynb: New file.
      * tests/Makefile.am, doc/org/tut.org: Add it.
      * NEWS: Mention these bindings.
      760bde09
  7. 08 Sep, 2020 2 commits
    • Alexandre Duret-Lutz's avatar
      game: make a propagate_players() function public · 9e8a8429
      Alexandre Duret-Lutz authored
      * bin/ltlsynt.cc (complete_env): Replace this function by...
      * spot/misc/game.hh, spot/misc/game.cc (propagate_players): ... this
      new one, hiding the "state-player" business from ltlsynt.  Also do not
      create a sink states unless necessary.
      * tests/core/ltlsynt.test: Adjust expected number of states.
      9e8a8429
    • Alexandre Duret-Lutz's avatar
      game: git rid of the parity_game class · 25c75c55
      Alexandre Duret-Lutz authored
      This class was a simple wrapper on top of twa_graph_ptr, but it's
      easier to simply use a twa_graph_ptr with a "state-player" property
      instead, this way we will be able to modify the automata I/O routines
      to support games directly.
      
      * spot/misc/game.cc, spot/misc/game.hh: Rewrite the solver and
      pg_printer interface.
      * bin/ltlsynt.cc: Adjust.
      * NEWS: Mention this change.
      * doc/org/concepts.org: Mention the state-player property.
      25c75c55
  8. 27 Jul, 2018 1 commit
    • Maximilien Colange's avatar
      ltlsynt: rework synthesis algorithms · bd75ab5b
      Maximilien Colange authored
      ltlsynt now offers two algorithms: one where splitting occurs before
      determinization (the historical one) and one where determinization
      occurs before splitting.
      
      * bin/ltlsynt.cc: here
      * tests/core/ltlsynt.test: test it and refactor test file
      * NEWS: document it
      * spot/misc/game.hh, spot/misc/game.cc: remove Calude's algorithm
      bd75ab5b
  9. 15 Jun, 2018 1 commit
    • Maximilien Colange's avatar
      ltlsynt: more deterministic behavior · 9489a65b
      Maximilien Colange authored
      Zielonka algorithm used to iterate over an std::unordered_set, thus
      producing different strategies depending on compiler...
      
      * spot/misc/game.cc: replace std::unordered_set with std::set
      9489a65b
  10. 23 Apr, 2018 2 commits
    • Maximilien Colange's avatar
      fix parity game printing · 9d34c1f5
      Maximilien Colange authored
      * spot/misc/game.cc: a state could be printed several times
      * tests/core/ltlsynt.test: update tests
      9d34c1f5
    • Maximilien Colange's avatar
      parity game: various improvements · 9698363e
      Maximilien Colange authored
      Zielonka algorithm has been fixed and optimized.
      It also now computes the strategy for both players.
      
      * bin/ltlsynt.cc: Update calls to parity_game::solve()
      * spot/misc/game.cc, spot/misc/game.hh: Implement the changes
      9698363e
  11. 21 Feb, 2018 1 commit
    • Alexandre Duret-Lutz's avatar
      include config.h in all *.cc files · ac6b0c94
      Alexandre Duret-Lutz authored
      This helps working around missing C functions like strcasecmp that do
      not exist everywhere (e.g. on Cygwin), and for which lib/ supplies a
      replacement.  Unfortunately we do not have such build in our current
      continuous integration suite, so we cannot easily detect files where
      such config.h inclusion would be useful.  Therefore this patch simply
      makes it mandatory to include config.h in *.cc files.  Including this
      in public *.hh file is currently forbidden.
      
      * spot/gen/automata.cc, spot/gen/formulas.cc,
      spot/kripke/fairkripke.cc, spot/kripke/kripke.cc,
      spot/ltsmin/ltsmin.cc, spot/misc/game.cc, spot/parseaut/fmterror.cc,
      spot/parsetl/fmterror.cc, spot/parsetl/parsetl.yy,
      spot/priv/bddalloc.cc, spot/priv/freelist.cc, spot/priv/satcommon.cc,
      spot/priv/trim.cc, spot/priv/weight.cc, spot/ta/ta.cc,
      spot/ta/taexplicit.cc, spot/ta/taproduct.cc, spot/ta/tgtaexplicit.cc,
      spot/ta/tgtaproduct.cc, spot/taalgos/dot.cc,
      spot/taalgos/emptinessta.cc, spot/taalgos/minimize.cc,
      spot/taalgos/reachiter.cc, spot/taalgos/statessetbuilder.cc,
      spot/taalgos/stats.cc, spot/taalgos/tgba2ta.cc, spot/tl/apcollect.cc,
      spot/tl/contain.cc, spot/tl/declenv.cc, spot/tl/defaultenv.cc,
      spot/tl/dot.cc, spot/tl/exclusive.cc, spot/tl/hierarchy.cc,
      spot/tl/length.cc, spot/tl/ltlf.cc, spot/tl/mark.cc,
      spot/tl/mutation.cc, spot/tl/nenoform.cc, spot/tl/print.cc,
      spot/tl/randomltl.cc, spot/tl/relabel.cc, spot/tl/remove_x.cc,
      spot/tl/simplify.cc, spot/tl/snf.cc, spot/tl/unabbrev.cc,
      spot/twa/acc.cc, spot/twa/bdddict.cc, spot/twa/bddprint.cc,
      spot/twa/formula2bdd.cc, spot/twa/taatgba.cc, spot/twa/twa.cc,
      spot/twa/twagraph.cc, spot/twa/twaproduct.cc, spot/twaalgos/aiger.cc,
      spot/twaalgos/alternation.cc, spot/twaalgos/are_isomorphic.cc,
      spot/twaalgos/bfssteps.cc, spot/twaalgos/canonicalize.cc,
      spot/twaalgos/cleanacc.cc, spot/twaalgos/cobuchi.cc,
      spot/twaalgos/complement.cc, spot/twaalgos/complete.cc,
      spot/twaalgos/compsusp.cc, spot/twaalgos/couvreurnew.cc,
      spot/twaalgos/cycles.cc, spot/twaalgos/degen.cc,
      spot/twaalgos/determinize.cc, spot/twaalgos/dot.cc,
      spot/twaalgos/dtbasat.cc, spot/twaalgos/dtwasat.cc,
      spot/twaalgos/dualize.cc, spot/twaalgos/emptiness.cc,
      spot/twaalgos/gtec/ce.cc, spot/twaalgos/gtec/gtec.cc,
      spot/twaalgos/gtec/sccstack.cc, spot/twaalgos/gtec/status.cc,
      spot/twaalgos/gv04.cc, spot/twaalgos/hoa.cc,
      spot/twaalgos/iscolored.cc, spot/twaalgos/isdet.cc,
      spot/twaalgos/isunamb.cc, spot/twaalgos/isweakscc.cc,
      spot/twaalgos/langmap.cc, spot/twaalgos/lbtt.cc,
      spot/twaalgos/ltl2taa.cc, spot/twaalgos/ltl2tgba_fm.cc,
      spot/twaalgos/magic.cc, spot/twaalgos/mask.cc,
      spot/twaalgos/minimize.cc, spot/twaalgos/neverclaim.cc,
      spot/twaalgos/parity.cc, spot/twaalgos/postproc.cc,
      spot/twaalgos/powerset.cc, spot/twaalgos/product.cc,
      spot/twaalgos/rabin2parity.cc, spot/twaalgos/randomgraph.cc,
      spot/twaalgos/randomize.cc, spot/twaalgos/reachiter.cc,
      spot/twaalgos/relabel.cc, spot/twaalgos/remfin.cc,
      spot/twaalgos/remprop.cc, spot/twaalgos/sbacc.cc,
      spot/twaalgos/sccfilter.cc, spot/twaalgos/sccinfo.cc,
      spot/twaalgos/se05.cc, spot/twaalgos/sepsets.cc,
      spot/twaalgos/simulation.cc, spot/twaalgos/split.cc,
      spot/twaalgos/stats.cc, spot/twaalgos/strength.cc,
      spot/twaalgos/stripacc.cc, spot/twaalgos/stutter.cc,
      spot/twaalgos/sum.cc, spot/twaalgos/tau03.cc,
      spot/twaalgos/tau03opt.cc, spot/twaalgos/totgba.cc,
      spot/twaalgos/toweak.cc, spot/twaalgos/translate.cc,
      spot/twaalgos/word.cc, tests/core/acc.cc, tests/core/bitvect.cc,
      tests/core/checkpsl.cc, tests/core/checkta.cc, tests/core/consterm.cc,
      tests/core/emptchk.cc, tests/core/equalsf.cc, tests/core/graph.cc,
      tests/core/ikwiad.cc, tests/core/intvcmp2.cc, tests/core/intvcomp.cc,
      tests/core/kind.cc, tests/core/kripkecat.cc, tests/core/length.cc,
      tests/core/ltlrel.cc, tests/core/ngraph.cc, tests/core/parity.cc,
      tests/core/randtgba.cc, tests/core/readltl.cc, tests/core/reduc.cc,
      tests/core/safra.cc, tests/core/sccif.cc, tests/core/syntimpl.cc,
      tests/core/taatgba.cc, tests/core/tostring.cc, tests/core/trival.cc,
      tests/core/twagraph.cc, tests/ltsmin/modelcheck.cc,
      spot/parseaut/scanaut.ll, spot/parsetl/scantl.ll: Include config.h.
      * spot/gen/Makefile.am, spot/graph/Makefile.am,
      spot/kripke/Makefile.am, spot/ltsmin/Makefile.am,
      spot/parseaut/Makefile.am, spot/parsetl/Makefile.am,
      spot/priv/Makefile.am, spot/ta/Makefile.am, spot/taalgos/Makefile.am,
      spot/tl/Makefile.am, spot/twa/Makefile.am, spot/twaalgos/Makefile.am,
      spot/twaalgos/gtec/Makefile.am, tests/Makefile.am: Add the -I lib/
      flags.
      * tests/sanity/includes.test: Catch missing config.h in *.cc, and
      diagnose config.h in *.hh.
      * tests/sanity/style.test: Better diagnostics.
      ac6b0c94
  12. 17 Nov, 2017 2 commits
  13. 25 Sep, 2017 3 commits
    • Thibaud Michaud's avatar
      parity game: compute winning strategy · 601e1405
      Thibaud Michaud authored
      * spot/misc/game.cc, spot/misc/game.hh: Here.
      * bin/ltlsynt.cc: Realizability is now done by checking if the winning
      strategy contains the initial state.
      601e1405
    • Thibaud Michaud's avatar
      parity game: add Zielonka's recursive algorithm · f414e9f5
      Thibaud Michaud authored
      * spot/misc/game.cc, spot/misc/game.hh: Implement it.
      * bin/ltlsynt.cc: Use it.
      * doc/org/ltlsynt.org: Document it.
      f414e9f5
    • Thibaud Michaud's avatar
      add ltlsynt executable · 0821c97e
      Thibaud Michaud authored
      For now, ltlsynt only handles LTL realizability. It uses a reduction to
      parity game followed by Calude et al.'s reduction from parity game to
      reachability game.
      
      * bin/ltlsynt.cc, bin/Makefile.am, bin/man/ltlsynt.x,
      bin/man/Makefile.am, bin/.gitignore: New binary.
      * doc/org/arch.tex, doc/Makefile.am, doc/org/tools.org,
      doc/org/ltlsynt.org: Document it.
      * spot/misc/game.cc, spot/misc/game.hh, spot/misc/Makefile.am: Parity
      game wrapper for parity automata + reachability game interface from
      Calude et al.'s paper.
      0821c97e