1. 08 Sep, 2020 1 commit
    • 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 17 Nov, 2017 2 commits
  7. 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