1. 06 Jan, 2017 12 commits
    • Alexandre GBAGUIDI AISSE's avatar
      spot: Add 'langmap' option with dichotomy (it helps to choose min val) · 67e3a4f2
      Alexandre GBAGUIDI AISSE authored
      * python/spot/__init__.py: Handle 'dicho' option in 'sat_minimize'.
      * spot/priv/satcommon.cc: Implement get_number_of_distinct_vals.
      * spot/priv/satcommon.hh: Declare get_number_of_distinct_vals.
      * spot/twaalgos/dtbasat.cc: Use get_number_of_distinct_vals.
      * spot/twaalgos/dtbasat.hh: Change dichotomy function's prototype.
      * spot/twaalgos/dtwasat.cc: Use get_number_of_distinct_vals.
      * spot/twaalgos/dtwasat.hh: Change dichotomy function's prototype.
      Handle options.
      * spot/twaalgos/postproc.cc: Handle options.
      * spot/twaalgos/postproc.hh: Add dicho_langmap_ var for options.
      * tests/core/satmin2.test: Add tests for dichotomy.
      * tests/core/satmin.test: Add tests for dichotomy.
      * tests/python/satmin.py: Replace 'dichotomy' with 'dicho' option.
    • Alexandre GBAGUIDI AISSE's avatar
      bin/autfilt.cc: Add '--highlight-languages' option · 7046a496
      Alexandre GBAGUIDI AISSE authored
      * bin/autfilt.cc: Add that option.
      * tests/core/highlightstate.test: Add test.
      * NEWS: Update.
    • Alexandre GBAGUIDI AISSE's avatar
      twaalgos: Implement language_map algo · 8a0eed6c
      Alexandre GBAGUIDI AISSE authored
      * python/spot/impl.i: Add python bindings.
      * spot/twaalgos/langmap.cc: Implement algo.
      * spot/twaalgos/langmap.hh: Declare algo.
      * spot/twaalgos/Makefile.am: Add new files.
      * tests/python/langmap.py: Add tests.
      * NEWS: Update.
    • Alexandre GBAGUIDI AISSE's avatar
      spot: Implement dt*a_sat_minimize_assume(...) methods · 9a204b77
      Alexandre GBAGUIDI AISSE authored
      * python/spot/__init__.py: Add 'assume' option.
      * spot/misc/satsolver.cc: Add function to handle assumptions.
      * spot/misc/satsolver.hh: Declare assumption function.
      * spot/twaalgos/dtbasat.cc: Implement dtba_sat_minimize_assume.
      * spot/twaalgos/dtbasat.hh: Declare it.
      * spot/twaalgos/dtwasat.cc: Implement dtwa_sat_minimize_assume and
      handle options.
      * spot/twaalgos/dtwasat.hh: Declare it.
      * spot/twaalgos/postproc.cc: Handle options.
      * spot/twaalgos/postproc.hh: Use param_ var for incr and assume.
      * tests/core/satmin.test: Add tests for the new function.
      * tests/core/satmin2.test: Add tests for the new function.
      * tests/python/satmin.py: Add tests for the new function.
    • Alexandre GBAGUIDI AISSE's avatar
      twaalgos: Implement dt*a_sat_minimize_incr(...) functions · ee17c2de
      Alexandre GBAGUIDI AISSE authored
      * python/spot/__init__.py: Add 'incr' boolean argument.
      * spot/twaalgos/dtbasat.cc: Implement dtba_sat_minimize_incr(...).
      * spot/twaalgos/dtbasat.hh: Declare it.
      * spot/twaalgos/dtwasat.cc: Implement dtwa_sat_minimize_incr(...) and
      deal with options.
      * spot/twaalgos/dtwasat.hh: Declare it.
      * spot/twaalgos/postproc.cc: Add option --sat-minimize=incr.
      * spot/twaalgos/postproc.hh: Add incr parameter.
      * tests/core/satmin.test: Add tests for incremental version.
      Update expected result.
      * tests/core/satmin2.test: Add tests for incremental version.
      * tests/python/satmin.py: Add tests for incremental version.
    • Alexandre GBAGUIDI AISSE's avatar
      twaalgos: Improve data storage in SAT-minimization · 9acd7370
      Alexandre GBAGUIDI AISSE authored
      * spot/misc/satsolver.hh: Make solver return vector<bool> instead of
      * spot/misc/satsolver.cc: Update code.
      * spot/priv/Makefile.am: Add satcommon.*
      * spot/priv/satcommon.hh: Declare helper class and factorize some
      duplicate code of dt*asat.cc
      * spot/priv/satcommon.cc: Implement helper class and factorize some
      duplicate code of dt*asat.cc
      * spot/twaalgos/dtbasat.cc: Declare helper, implement some functions
      in dict struct and update code.
      * spot/twaalgos/dtwasat.cc: Declare helper, implement some functions
      in dict struct and update code.
      * tests/core/readsat.cc: Update tests.
      * tests/core/satmin.test: Typo.
      * tests/core/satmin2.test: Update an expected result.
    • Alexandre GBAGUIDI AISSE's avatar
      twaalgos: Help sat_build to ignore unuseful transitions · 79f4c8e0
      Alexandre GBAGUIDI AISSE authored
      * spot/twaalgos/dtbasat.cc: Fix static sat_build.
      * spot/twaalgos/dtwasat.cc: Fix static sat_build.
    • Alexandre GBAGUIDI AISSE's avatar
      tests: Improve tests related to SAT-minimization · dfd500a5
      Alexandre GBAGUIDI AISSE authored
      * tests/core/satmin.test: Delete check for SPOT_SATSOLVER env
      variable and add state numbers verification.
      * tests/core/satmin2.test: Delete check for SPOT_SATSOLVER
      env variable.
      * tests/python/satmin.py: Delete check for SPOT_SATSOLVER
      env variable.
    • Alexandre GBAGUIDI AISSE's avatar
      spot: Add Picosat to Spot library & Update satsolver class · 32f040fa
      Alexandre GBAGUIDI AISSE authored
      * Makefile.am: Add picosat to subdirs.
      * configure.ac: Add picosat/Makefile to AC_CONFIG_FILES.
      * README: Add picosat/ in the list of directories.
      * debian/copyright: Add picosat licence and details.
      * picosat/Makefile.am: Implement Makefile.am in picosat directory.
      * spot/Makefile.am: Tell the compiler to add libpico.la into libspot.la.
      * picosat/LICENSE: Add picosat licence.
      * picosat/NEWS: Add picosat NEWS.
      * picosat/VERSION: Add picosat VERSION.
      * picosat/picosat.c: Add picosat c file.
      * picosat/picosat.h: Add picosat header file.
      * spot/misc/satsolver.cc: Update functions.
      * spot/misc/satsolver.hh: Add documentation, clean code, change
      some functions visibility and separate templates functions.
      * spot/twaalgos/dtbasat.cc: Update dtba_to_sat function.
      * spot/twaalgos/dtwasat.cc: Update dtwa_to_sat function.
    • Alexandre GBAGUIDI AISSE's avatar
      spot: Abstract cnf writing in SAT-based minimisation · 596bdec9
      Alexandre GBAGUIDI AISSE authored
      * spot/misc/satsolver.hh: Declare all functions needed.
      * spot/misc/satsolver.cc: Implement them.
      * spot/twaalgos/dtbasat.cc: Abstract writing.
      * spot/twaalgos/dtwasat.cc: Abstract writing.
    • Alexandre GBAGUIDI AISSE's avatar
      .gitignore: Fix typo · f2e091b9
      Alexandre GBAGUIDI AISSE authored
      * .gitignore: Fix typo dt*a instead of dt*ba.
    • Alexandre Duret-Lutz's avatar
      tests: update ipnbdoctest to graphviz 2.40 and Python 3.6 · 32086f7c
      Alexandre Duret-Lutz authored
      This fix recent failures observed on arch linux because
      it uses newer versions of graphviz and Python.
      * tests/python/ipnbdoctest.py (sanitize): More substitutions.
  2. 01 Jan, 2017 1 commit
  3. 30 Dec, 2016 3 commits
    • Alexandre Duret-Lutz's avatar
      twa: add prop_set::improve_det · 684c9c47
      Alexandre Duret-Lutz authored
      Algorithms that remove transitions can turn a non-deterministic
      automaton into a deterministic one, so we need to be able to specify
      that determinism can be improved (as opposed to preserved).
      * spot/twa/twa.hh (twa::prop_set::improve_det): New attribute.
      (twa::prop_keep, twa::prop_copy): Honor it.
      * spot/tl/exclusive.cc, spot/twaalgos/alternation.cc,
      spot/twaalgos/complete.cc, spot/twaalgos/degen.cc,
      spot/twaalgos/determinize.cc, spot/twaalgos/mask.cc,
      spot/twaalgos/minimize.cc, spot/twaalgos/remfin.cc,
      spot/twaalgos/remprop.cc, spot/twaalgos/sbacc.cc,
      spot/twaalgos/sccfilter.cc, spot/twaalgos/simulation.cc,
      spot/twaalgos/strength.cc, spot/twaalgos/stutter.cc,
      spot/twaalgos/totgba.cc: Adjust calls to prop_keep() and
    • Alexandre Duret-Lutz's avatar
      simulation: does not preserve !unambiguous, !semi-deterministic · ada81853
      Alexandre Duret-Lutz authored
      * spot/twaalgos/simulation.cc: Reset those to maybe.
      * tests/core/semidet.test: Add some tests.
    • Alexandre Duret-Lutz's avatar
  4. 29 Dec, 2016 16 commits
    • Alexandre Duret-Lutz's avatar
      support for semi-deterministic property · 4b013878
      Alexandre Duret-Lutz authored
      * spot/twa/twa.hh (prop_semi_deterministic): New methods.
      * spot/parseaut/parseaut.yy, spot/twaalgos/hoa.cc: Add support for the
      semi-deterministic property.
      * doc/org/concepts.org, doc/org/hoa.org: Document it.
      * spot/twaalgos/isdet.cc,
      spot/twaalgos/isdet.hh (is_semi_deterministic): New function.
      * bin/autfilt.cc: Add --is-semi-deterministic.
      * bin/common_aoutput.cc: Add --check=semi-deterministic.
      * tests/core/semidet.test: New file.
      * tests/Makefile.am: Add it.
      * tests/core/parseaut.test, tests/core/readsave.test: Adjust.
    • Alexandre Duret-Lutz's avatar
      twa_graph: support alternation in remove_dead/unreachable_states · db5d9780
      Alexandre Duret-Lutz authored
      * spot/graph/graph.hh (internal::univ_dest_mapper): New helper class.
      * spot/twa/twagraph.cc (merge_univ_dests): Simplify using
      (purge_unreachable_states, purge_dead_states): Add support for
      * tests/core/alternating.test: More tests.
    • Alexandre Duret-Lutz's avatar
      autfilt: handle alternation with --equivalent-to and friends · 096c78a3
      Alexandre Duret-Lutz authored
      * bin/autfilt.cc (ensure_deterministic): Remove alternation on demand.
      (process_automaton): Prefer twa::intersects() over
      * spot/twa/twa.cc (remove_fin_maybe): Also remove alternation.
      * tests/core/alternating.test: More tests.
    • Alexandre Duret-Lutz's avatar
      autfilt: add --is-alternating · 77ce4170
      Alexandre Duret-Lutz authored
      * bin/autfilt.cc: Implement --is-alternating.
      * tests/core/complete.test: Test it.
      * NEWS: Mention it.
    • Alexandre Duret-Lutz's avatar
      autfilt: add --is-very-weak · 6a11e149
      Alexandre Duret-Lutz authored
      * bin/autfilt.cc: Implement --is-very-weak.
      * tests/core/strength.test: Test it.
      * NEWS: Mention it.
    • Alexandre Duret-Lutz's avatar
      twa_graph: add a merge_univ_dests() method · 12f6c8cf
      Alexandre Duret-Lutz authored
      and call it after parsing
      * spot/twa/twagraph.cc, spot/twa/twagraph.hh
      (twa_graph::merge_univ_dests): New method.
      * spot/parseaut/parseaut.yy: Call it.
      * spot/twaalgos/dot.cc: Improve output, now that
      several edges can use the same universal destination.
      * tests/core/alternating.test, tests/core/complete.test,
      tests/core/parseaut.test, tests/python/_altscc.ipynb,
      tests/python/alternating.py, tests/python/alternation.ipynb: Adjust
      test case.
      * doc/org/tut24.org: Adjust example.
    • Alexandre Duret-Lutz's avatar
      org: examples with alternating automata · 3d0a971a
      Alexandre Duret-Lutz authored
      * doc/org/tut23.org, doc/org/tut24.org, doc/org/tut31.org: New files.
      * doc/Makefile.am, doc/org/tut.org: Add them.
      * doc/org/hoa.org, doc/org/concepts.org: Adjust for alternation support.
      * NEWS: Add links.
    • Alexandre Duret-Lutz's avatar
      remfin: call remove_alternation if needed · f5b261d8
      Alexandre Duret-Lutz authored
      * spot/twaalgos/remfin.cc: Here.
      * tests/core/alternating.test: Add a test case.
    • Alexandre Duret-Lutz's avatar
      complete: add support for alternating autamata · 071d819c
      Alexandre Duret-Lutz authored
      * spot/twaalgos/complete.cc: Do not use the initial
      state as a sink if it is universal.
      * tests/core/complete.test: Add a test case.
    • Alexandre Duret-Lutz's avatar
      postproc: preliminary support for alternating automata · f1b8d5f1
      Alexandre Duret-Lutz authored
      * spot/twaalgos/postproc.cc: Call remove_alternation().
      * tests/core/alternating.test: Additional test.
    • Alexandre Duret-Lutz's avatar
      twaalgos: add many guards against alternation · 9f6924cc
      Alexandre Duret-Lutz authored
      * spot/twa/twagraph.hh, spot/twaalgos/are_isomorphic.cc,
      spot/twaalgos/canonicalize.cc, spot/twaalgos/couvreurnew.cc,
      spot/twaalgos/cycles.cc, spot/twaalgos/degen.cc,
      spot/twaalgos/determinize.cc, spot/twaalgos/isunamb.cc,
      spot/twaalgos/isweakscc.cc, spot/twaalgos/mask.hh,
      spot/twaalgos/minimize.cc, spot/twaalgos/product.cc,
      spot/twaalgos/randomize.cc, spot/twaalgos/sbacc.cc,
      spot/twaalgos/sccfilter.cc, spot/twaalgos/simulation.cc:
      Throw a runtime_error if the input is alternating.
    • Alexandre Duret-Lutz's avatar
      ltlcross: add support for alternating automata · 87c9d6f0
      Alexandre Duret-Lutz authored
      * bin/ltlcross.cc: Add an alternation-removal pass, and
      adjust CSV output.
      * doc/org/ltlcross.org: Update.
      * tests/core/ltl3dra.test, tests/core/ltl3ba.test: Add more tests.
      * tests/Makefile.am: Add tests/core/ltl3ba.test.
      * NEWS: Mention it.
    • Alexandre Duret-Lutz's avatar
      stats: add a variant for twa_graph_ptr · 543e0db9
      Alexandre Duret-Lutz authored
      This is faster than using the abstract interface, and it also supports
      alternating automata.  (This will be tested in the tests for
      ltlcross's support for alternating automata.)
      * spot/twaalgos/stats.cc (stats_reachable, sub_stats_reachable):
      Add code specific to twa_graph_ptr.
    • Alexandre Duret-Lutz's avatar
      remfin: ignore unreachable states in remove_fin_weak() · 64fa6c00
      Alexandre Duret-Lutz authored
      * spot/twaalgos/remfin.cc (remove_fin_weak): Ignore unreachable
      states.  This caused crashes in the test cases for the
      upcoming alternation support in ltlcross.
    • Alexandre Duret-Lutz's avatar
    • Alexandre Duret-Lutz's avatar
      alternation: implement remove_alternation() for weak alt automata · fa06cfa3
      Alexandre Duret-Lutz authored
      This mixes the subset construction (for 1-state rejecting SCCs) and
      the breakpoint construction (for larger rejecting SCCs).  The
      algorithm should probably be rewritten in a cleaner and more efficient
      way, but that should do for a first version.  It should be easy to
      extend it to support Büchi acceptance (since the breakpoint
      construction works for this) when we need it.
      * spot/twaalgos/alternation.hh,
      spot/twaalgos/alternation.cc (remove_alternation): New function.
      * tests/python/alternation.ipynb: New file.
      * tests/Makefile.am, doc/org/tut.org: Add it.
  5. 27 Dec, 2016 8 commits
    • Alexandre Duret-Lutz's avatar
      twa: add support for very-weak property · 582d455c
      Alexandre Duret-Lutz authored
      * spot/twa/twa.hh: Implement the property.
      * spot/parseaut/parseaut.yy, spot/twaalgos/hoa.cc: Add input
      and output for it.
      * spot/twaalgos/strength.cc,
      spot/twaalgos/strength.hh (is_very_weak_automaton): New function.
      * tests/core/alternating.test: Add a test for --check=strength
      on an alternating automaton.
      * tests/core/strength.test, tests/core/parseaut.test: Adjust expected
      * NEWS, doc/org/hoa.org, doc/org/concepts.org: Document it.
    • Alexandre Duret-Lutz's avatar
      sccinfo: adjust to work with alternating automata · a4ce9994
      Alexandre Duret-Lutz authored
      * spot/twaalgos/sccinfo.cc: Consider universal edges as if they were
      existential edges.
      * spot/twaalgos/sccinfo.hh: Document that.
      * spot/twaalgos/dot.cc: Allow option 's' again, for easy testing.
      * tests/core/alternating.test: Adjust tests.
      * tests/python/_altscc.ipynb: New file (more tests).
      * tests/Makefile.am: Add it.
    • Alexandre Duret-Lutz's avatar
      parseaut: handle alternating automata with many universal init states · d2f471da
      Alexandre Duret-Lutz authored
      * spot/parseaut/parseaut.yy (fix_initial_state): Use
      spot::internal::outgoing_edge_group to reduce all initial states to a
      single one.
      * tests/core/parseaut.test: Add more tests.
    • Alexandre Duret-Lutz's avatar
      alternation: add a states_and algorithm · 27ab631c
      Alexandre Duret-Lutz authored
      This should will come handy to implement the convertion from LTL to
      alternating automata, and to handle automata with multiple initial
      * spot/twaalgos/alternation.hh, spot/twaalgos/alternation.cc: New files.
      * spot/twaalgos/Makefile.am: Add them.
      * python/spot/impl.i: Add bindings.
      * tests/python/alternating.py: Test states_and.
    • Alexandre Duret-Lutz's avatar
      twa_graph: add support for universal initial states · 48c812a5
      Alexandre Duret-Lutz authored
      The only missing point is that the HOA parser cannot deal with multiple
      universal initial states, as seen in parseaut.test.
      * spot/graph/graph.hh (new_univ_dests): New function, extracted from...
      (new_univ_edge): ... this one.
      * spot/twa/twagraph.hh (set_univ_init_state): Implement using
      * spot/twaalgos/dot.cc, spot/twaalgos/hoa.cc, python/spot/impl.i:
      Add support for universal initial states.
      * spot/parseaut/parseaut.yy: Add preliminary support for
      universal initial states.  Multiple universal initial states
      are still not supported.
      * tests/core/alternating.test, tests/core/parseaut.test,
      tests/python/alternating.py: Adjust tests and exercise this new feature.
    • Alexandre Duret-Lutz's avatar
      dot: add support for alternating automata · d5c9c345
      Alexandre Duret-Lutz authored
      * spot/twaalgos/dot.cc: Handle universal destinations.
      Ignore option 's' for alternating automata.
      * tests/core/alternating.test: New file.
      * tests/Makefile.am: Add it.
    • Alexandre Duret-Lutz's avatar
      parseaut: preliminary support for reading alternating automata · e6203686
      Alexandre Duret-Lutz authored
      Currently this only reads universal branches.  The parser (and the
      automaton code) do not support universal initial states.
      * spot/parseaut/parseaut.yy: Read universal branches.  Deal with
      the no-univ-branch/!univ-branch change in HOA 1.1.
      * tests/python/alternating.py: Read the output of print_hoa.
      * tests/core/parseaut.test: Adjust test output, and add more tests.
    • Alexandre Duret-Lutz's avatar
      print_hoa: add support for universal branches · 56df459c
      Alexandre Duret-Lutz authored
      * spot/twaalgos/hoa.cc: Implement it.
      * tests/python/alternating.py: Test it.