1. 29 Dec, 2016 4 commits
    • 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.
      543e0db9
    • 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.
      64fa6c00
    • 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.
      fa06cfa3
  2. 27 Dec, 2016 10 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
      output.
      * NEWS, doc/org/hoa.org, doc/org/concepts.org: Document it.
      582d455c
    • 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.
      a4ce9994
    • 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.
      d2f471da
    • 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
      states.
      
      * 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.
      27ab631c
    • 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
      new_univ_dests.
      * 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.
      48c812a5
    • 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.
      d5c9c345
    • 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.
      e6203686
    • 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.
      56df459c
    • Alexandre Duret-Lutz's avatar
      twa_graph: add basic support for alternation · 6aad559c
      Alexandre Duret-Lutz authored
      This only allows creating universal edges, and reading the associated
      destinations.
      
      * spot/twa/twagraph.hh (new_univ_edges, univ_dests, is_alternating): New
      function.
      * python/spot/impl.i: Add Python bindings.
      * tests/python/alternating.py: New file.
      * tests/Makefile.am: Add it.
      6aad559c
    • Alexandre Duret-Lutz's avatar
      graph: replace the existing "alternating" interface · 4903f086
      Alexandre Duret-Lutz authored
      * spot/graph/graph.hh: Use the sign bit of destination state X to
      designate a universal edge.  Store the destinations of such an edge in a
      separate array, at index ~X.
      * spot/graph/ngraph.hh, tests/core/graph.cc, tests/core/graph.test,
      tests/core/ngraph.cc: Adjust test case to the new interface.
      4903f086
  3. 25 Dec, 2016 1 commit
  4. 24 Dec, 2016 3 commits
  5. 16 Dec, 2016 5 commits
  6. 15 Dec, 2016 3 commits
  7. 14 Dec, 2016 1 commit
  8. 13 Dec, 2016 3 commits
  9. 10 Dec, 2016 2 commits
  10. 09 Dec, 2016 1 commit
    • Alexandre Duret-Lutz's avatar
      ltlf: ensure alive holds initially · 413eab1d
      Alexandre Duret-Lutz authored
      Reported by Shufang Zhu.
      
      * spot/tl/ltlf.cc, spot/tl/ltlf.hh: Fix the transltion
      and update the comments.
      * tests/core/ltlfilt.test: Adjust test cases.
      * NEWS: Mention the fix.
      * THANKS: Add Shufang Zhu.
      413eab1d
  11. 02 Dec, 2016 2 commits
    • Alexandre Duret-Lutz's avatar
      install back the safety check of includes.test · 7824005d
      Alexandre Duret-Lutz authored
      Compilation of each header file alone, as a safety check, was removed
      when introducing "#pragma once" because we did not have to check for
      possible double inclusion.  However we still need to compile each
      header to make sure they are self-contained.
      
      * tests/sanity/includes.test: Compile each header.
      * tests/run.in: Export various compiler and directory flags.
      * spot/twaalgos/emptiness_stats.hh, spot/misc/mspool.hh,
      spot/misc/fixpool.hh: Include <spot/misc/common.hh>.
      * spot/misc/common.hh: Include <cassert>.
      * NEWS: Mention the fixed headers.
      7824005d
    • Alexandre Duret-Lutz's avatar
      install back the safety check of includes.test · 0ab8dc06
      Alexandre Duret-Lutz authored
      Compilation of each header file alone, as a safety check, was removed
      when introducing "#pragma once" because we did not have to check for
      possible double inclusion.  However we still need to compile each
      header to make sure they are self-contained.
      
      * tests/sanity/includes.test: Compile each header.
      * tests/run.in: Export various compiler and directory flags.
      * spot/twaalgos/emptiness_stats.hh, spot/misc/mspool.hh,
      spot/misc/fixpool.hh: Include <spot/misc/common.hh>.
      * spot/misc/common.hh: Include <cassert>.
      * NEWS: Mention the fixed headers.
      0ab8dc06
  12. 01 Dec, 2016 5 commits