1. 09 Feb, 2011 1 commit
  2. 07 Feb, 2011 1 commit
  3. 06 Feb, 2011 1 commit
  4. 04 Feb, 2011 1 commit
    • Alexandre Duret-Lutz's avatar
      Add a way to count the number of sub-transitions. · 30727074
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/stats.hh (tgba_sub_statistics): New class.
      (sub_stats_reachable): New function.
      * src/tgbaalgos/stats.cc (sub_stats_bfs): New class.
      (tgba_sub_statistics::dump, sub_stats_reachable): New function.
      * src/tgbatest/ltl2tgba.cc (-kt): New option.
      * src/tgbatest/ltl2tgba.test: Use -kt.
      30727074
  5. 03 Feb, 2011 1 commit
    • Alexandre Duret-Lutz's avatar
      Read guard of the form !(x) in neverclaims. · 91e51c4c
      Alexandre Duret-Lutz authored
      So far all neverclaims encountered would use (!(x)), but the
      files from the Büchi store do not.
      
      * src/neverparse/neverclaimscan.ll: Accept ! in front of guard,
      so that we can read Promela files from Goal's Büchi store.
      * src/tgbatest/neverclaimread.test: Test it.
      91e51c4c
  6. 01 Feb, 2011 1 commit
  7. 28 Jan, 2011 1 commit
    • Alexandre Duret-Lutz's avatar
      Fixup minimize_monitor(). · ad93f875
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/minimize.cc (minimize_monitor): Fix typo yielding
      incorrect monitor if the input tgba is not deterministic.
      * src/tgbatest/ltl2tgba.test: Add test case.
      ad93f875
  8. 27 Jan, 2011 2 commits
    • Alexandre Duret-Lutz's avatar
      Report formulas that are both safety and guarantee. · c8140de9
      Alexandre Duret-Lutz authored
      * src/tgbatest/ltl2tgba.cc (-O): Report formulas that are both
      safety and guarantee.
      * src/tgbatest/obligation.test: Add cases.
      c8140de9
    • Alexandre Duret-Lutz's avatar
      Rename is_safety_automaton() as is_guarantee_automaton() and · db124d02
      Alexandre Duret-Lutz authored
      implement is_safety_mwdba().
      
      Note: I swapped the name of safety and guarantee when I
      implemented is_safety_automaton() on 2010-03-20.  Fortunately,
      is_safety_automaton() was only used where is_guarantee_automaton()
      would have been correct.
      
      * src/tgbaalgos/safety.cc (is_guarantee_automaton): Rename as ...
      (is_guarantee_automaton): ... this.
      (is_safety_mwdba): New function.
      * src/tgbaalgos/safety.hh: Adjust and add documentation.
      * src/tgbaalgos/minimize.cc: Use is_guarantee_automaton() instead
      of is_safety_automaton().
      * src/tgbatests/safety.test: Rename as ...
      * src/tgbatests/obligation.test: ... this, and augment the
      test.
      * src/tgbatest/Makefile.am: Adjust.
      * src/tgbatest/ltl2tgba.cc (-O): Display whether a formula
      represent a safety, guarantee, or obligation property.
      * NEWS: Adjust.
      db124d02
  9. 06 Jan, 2011 2 commits
    • Alexandre Duret-Lutz's avatar
      '([]a && XXXX!a)' was not properly minimized because its · 256eb5bb
      Alexandre Duret-Lutz authored
      translation contain useless SCCs that where not ignored for
      minimization.
      
      * src/tgbaalgos/minimize.cc (minimize_wdba): Strip useless
      SCCs before minimization.
      * src/tgbatest/ltl2tgba.test: Add a check.
      256eb5bb
    • Alexandre Duret-Lutz's avatar
      The neverclaim output by spin -f '([]a && XXXX!a)' was not · df2a950e
      Alexandre Duret-Lutz authored
      understood by Spot.
      
      * src/neverparse/neverclaimparse.yy: Support "if :: false fi;"
      instructions.  Spin sometimes output these on dead states.
      Also rewrite the "transitions" rule as a left recursion.
      * src/tgbatest/neverclaimread.test: Adjust output because
      of the right->left recursion change, and add two more formula
      to submit to Spin to test its output.
      df2a950e
  10. 05 Jan, 2011 15 commits
    • Alexandre Duret-Lutz's avatar
      * src/tgbatest/Makefile.am: Remove the unused minimize program. · b9dd72b2
      Alexandre Duret-Lutz authored
      * src/tgbatest/minimize.cc: Delete.
      b9dd72b2
    • Alexandre Duret-Lutz's avatar
      Cleanup the minimize.hh interface. · 8c972ad3
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/minimize.hh, src/tgbaalgos/minimize.cc
      (minimize): Split into ...
      (minimize_wdba, minimize_monitor): ... these two functions.
      * src/tgbatest/ltl2tgba.cc (main): Adjust the call to
      minimize_monitor.
      * wrap/python/cgi-bin/ltl2tgba.in: Adjust the calls to
      minimize_monitor and minimize_obligation.
      * wrap/python/spot.i: Declare minimize_monitor, minimize_wdba,
      minimize_obligations.
      * src/tgba/tgbaexplicit.hh (tgba_explicit_string)
      (tgba_explicit_formula, tgba_explicit_number): Add fake
      declarations so that SWIG can see they inherits from tgba.
      8c972ad3
    • Alexandre Duret-Lutz's avatar
      * src/tgbatest/spotlbtt.test: Add test for -l -R3b, showing many · f4e583d0
      Alexandre Duret-Lutz authored
      failure because the minimization() algorithm is currently
      incorrect when applied to non-weak automata.
      f4e583d0
    • Alexandre Duret-Lutz's avatar
      Move the logic for detecting when the minimize() algorithm is · 907d173d
      Alexandre Duret-Lutz authored
      correct from ltl2tgba to the library.
      
      * src/tgbaalgos/minimize.hh,
      src/tgbaalgos/minimize.cc (minimize_obligation): New function.
      * src/tgbatests/ltl2tgba.cc (main): Fix constness of automata,
      and call minimize_obligation() for -R3b.
      907d173d
    • Alexandre Duret-Lutz's avatar
      Speed up wdba.test, it was too slow for our buildfarm. · d72a2f0a
      Alexandre Duret-Lutz authored
      * src/tgbatest/wdba.test: Speed up execution by running only a
      couple of formula with valgrind.  Half of those with`-l -R3b' and
      the other half with `-f -R3'.
      d72a2f0a
    • Alexandre Duret-Lutz's avatar
      * src/tgbatest/ltl2tgba.cc (syntax): Regroup -M, -s, and -S option · 0392058e
      Alexandre Duret-Lutz authored
      under the same heading "automaton conversion".
      0392058e
    • Alexandre Duret-Lutz's avatar
      Preliminary support for monitors. · cc8dd49d
      Alexandre Duret-Lutz authored
      * src/tgbatest/ltl2tgba.cc (-M): New option for building
      deterministic monitors.
      * src/tgbaalgos/minimize.cc (minimize): Take a monitor
      argument and adjust the code.
      * src/tgbaalgos/minimize.hh (minimize): Document it.
      cc8dd49d
    • Alexandre Duret-Lutz's avatar
      "ltl2tgba -Rm -X foo.tgba" would fail. · a962bb6d
      Alexandre Duret-Lutz authored
      * src/tgbatest/ltl2tgba.cc (main): Warn if -Rm is used without
      knowing the formula whose automaton is minimized.
      a962bb6d
    • Alexandre Duret-Lutz's avatar
      Fix bugs in minimize(). · 7d8a5310
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/minimize.cc (init_sets, minimize): Fix memory
      leaks and a usage of the wrong automaton.
      * src/tgbatest/wdba.test: Try using -Rm with -R3 or -R3b, and with
      valgrind.  This caught all the bugs fixed above.
      7d8a5310
    • Alexandre Duret-Lutz's avatar
      Fix bugs in minimize(), caught by spotlbtt.test. · 72139fd7
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/minimize.cc (minimize): Don't add acceptance
      conditions if the final set is empty.
      * src/tgbaalgos/powerset.cc (tgba_powerset): Add the initial state
      to acc_list if it is accepting.  Also do not compute an SCC build
      map if we don't have to build acc_list.
      72139fd7
    • Alexandre Duret-Lutz's avatar
      "ltl2tgba -Rm" will apply WDBA-minimization only if correct. · 54e10c25
      Alexandre Duret-Lutz authored
      * src/tgbatest/ltl2tgba.cc (main): Use WDBA-minimization only when
      it is correct. Either we can quickly determine that a formula or
      its negation is a safety formula, or we can slowly check the
      equivalence of the WDBA-minimized automaton and the original
      automaton.
      * src/tgbatest/wdba.test: New test.
      * src/tgbatest/safety.test: Adjust comment.
      * src/tgbatest/spotlbtt.test: Use -Rm.
      * src/tgbatest/Makefile.am (TESTS): Add wdba.test.
      54e10c25
    • Alexandre Duret-Lutz's avatar
      Better resource handling in minimization. · f9e84ac2
      Alexandre Duret-Lutz authored
      * src/tgbatest/ltl2tgba.cc (main): Delete the minimized automaton.
      * src/tgbaalgos/minimize.cc (minimize): Remove the call to
      unregister_variable() at the end.  It was both
      wrong (unregistering only the first variable) and useless ("delete
      del_a" will unregister all these variables).  Use a map and a set
      to keep track of free BDD variable and reuse them, otherwise the
      algorithm would sometimes use more variables than allocated.
      f9e84ac2
    • Alexandre Duret-Lutz's avatar
      Implement is_safety_automaton(). · 0af8d032
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/safety.hh, src/tgbaalgos/safety.cc: New
      files.
      * src/tgbaalgos/Makefile.am: Add them.
      * src/tgbatests/ltl2tgba.cc: Add option "-O".
      * src/tgbaalgos/scc.hh: Update documentation.
      * src/tgbatest/Makefile.am (TESTS): Add safety.test.
      * src/tgbatest/safety.test: New file.
      0af8d032
    • Felix Abecassis's avatar
      Small fixes. · 52090e48
      Felix Abecassis authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * src/tgbatest/minimize.cc: Delete useless includes.
      * src/tgbaalgos/minimize.cc: Delete useless includes,
      fixed acceptance conditions.
      * src/tgbatest/ltl2tgba.cc: Add -Rm option for minimization.
      * src/tgba/tgbaexplicit.cc: Fixed typo.
      52090e48
    • Felix Abecassis's avatar
      Test program for the minimization algorithm. · fac30eb0
      Felix Abecassis authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * src/tgbatest/minimize.cc: New file.  Minimize an automaton
      from a LTL formula and compare the size of the initial automaton
      to the size of the minimized automaton.
      fac30eb0
  11. 12 Dec, 2010 1 commit
    • Alexandre Duret-Lutz's avatar
      Merge transitions in tgba_tba_proxy. · 01843379
      Alexandre Duret-Lutz authored
      With this change the output of
      ltl2tgba -f -x -k -DS "GF(p_1) & ... & GF(p_n)
      uses less than (n+1)^2 transitions when it used
      exactly (n+1)*(2^n) transitions before.
      
      * src/tgba/tgbatba.cc (tgba_tba_proxy_succ_iterator): Merge
      transitions going to the same states if they are both accepting or
      if neither are.
      (state_ptr_bool_t, state_ptr_bool_less_than): Helper type to
      store a transition in tgba_tba_proxy_succ_iterator.
      * src/tgba/tgbatba.cc, src/tgba/tgbatba.hh
      (tgba_tba_proxy::transition_annotation): Remove.  We cannot
      implement this method if transitions are merged.
      01843379
  12. 10 Dec, 2010 1 commit
  13. 01 Dec, 2010 1 commit
  14. 30 Nov, 2010 2 commits
    • Alexandre Duret-Lutz's avatar
      Rationalize options for counter-example output. · 75a24111
      Alexandre Duret-Lutz authored
      * src/tgbatest/ltl2tgba.cc (main): Either replay the accepting
      run or print it, but do not do both.
      * src/tgbatest/emptchk.test: Adjust. I.e. use -C instead of -CR
      when we expect the run to be displayed.
      75a24111
    • Alexandre Duret-Lutz's avatar
      Fix a GCC 4.6 warning. · ae03bc67
      Alexandre Duret-Lutz authored
      * src/tgbatest/randtgba.cc (main): Remove the set but unused opt_A
      variable (the upcoming GCC 4.6 would warn about it) and set opt_ec
      to 1 if -A is used without -e.
      ae03bc67
  15. 27 Nov, 2010 2 commits
  16. 25 Nov, 2010 2 commits
  17. 06 Nov, 2010 5 commits