1. 08 Sep, 2013 2 commits
    • Alexandre Duret-Lutz's avatar
      rename dba_complement() to dtgba_complement() · 7a7ed8a6
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/dbacomp.cc, src/tgbaalgos/dbacomp.hh
      (dba_complement): Rename to...
      * src/tgbaalgos/dtgbacomp.cc, src/tgbaalgos/dtgbacomp.hh
      (dtgba_complement): ... this.
      * src/tgbaalgos/minimize.cc, src/tgbaalgos/powerset.cc,
      src/tgbatest/ltl2tgba.cc, src/bin/ltlcross.cc,
      src/tgbaalgos/Makefile.am: Adjust to name change.
      7a7ed8a6
    • Alexandre Duret-Lutz's avatar
      satmin: cleanup interfaces and minimization loops · fdb157bf
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/dtbasat.cc, src/tgbaalgos/dtbasat.hh:
      (dtba_sat_minimize): Split into...
      (dtba_sat_synthetize, dtba_sat_minimize): These.
      (dtba_sat_minimize_dichotomy): New function.
      * src/tgbaalgos/dtgbasat.cc, src/tgbaalgos/dtgbasat.hh
      (dtgba_sat_minimize, dtgba_sat_synthetize): Likewise.
      * src/tgbatest/ltl2tgba.cc: Adjust to new interface.
      * src/tgbaalgos/postproc.cc, src/tgbaalgos/postproc.hh:
      Cleanup option processing for SAT options.
      * src/tgbatest/satmin.test: Adjust.
      * src/bin/spot-x.cc, src/bin/man/spot-x.x, NEWS: Document.
      fdb157bf
  2. 26 Aug, 2013 24 commits
    • Alexandre Duret-Lutz's avatar
      postproc: disable WDBA-minimization on request · b09ef5be
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/postproc.cc, src/tgbaalgos/postproc.hh:
      Implement the wdba-minimize option.
      * src/bin/spot-x.cc (wdba-minimize): Document.
      * src/bin/man/spot-x.x: Update references.
      b09ef5be
    • Alexandre Duret-Lutz's avatar
      stats: add %r to display run-time · bfbe5b44
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/stats.cc, src/tgbaalgos/stats.hh: Add
      support for printing run-time.
      * src/bin/ltl2tgba.cc, src/bin/dstar2tgba.cc: Compute
      the run-time and show the option.
      * NEWS: Mention it.
      bfbe5b44
    • Alexandre Duret-Lutz's avatar
      isdet: simplify is_deterministic(), add is_complete(). · 4dd8d802
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/isdet.cc: Simplify determinism check.
      * src/tgbaalgos/isdet.hh, src/tgbaalgos/isdet.cc (is_complete): New
      function.
      * src/tgbaalgos/stats.cc, src/tgbaalgos/stats.hh, src/bin/dstar2tgba.cc
      src/bin/ltl2tgba.cc: Add escape sequence %p to the possible statistics
      to show whether an automaton is complete.
      * src/tgbatest/nondet.test: Add a couple more tests.
      4dd8d802
    • Alexandre Duret-Lutz's avatar
      sat: improve our algorithms · bcd794c6
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/dtbasat.cc, src/tgbaalgos/dtbasat.hh:
      Rename dba_sat_minimize to dtba_sat_minimize.
      Make it possible to produce state-based automata, and do
      not output useless clauses.
      * src/tgbaalgos/dtgbasat.cc, src/tgbaalgos/dtgbasat.hh:
      likewise, but also add the possibility to set the
      target number of states, as in dtba_sat_minimize.
      * src/tgbaalgos/postproc.cc, src/tgbaalgos/postproc.hh:
      Add new options for state-based computations and
      setting acceptance and states number when using
      dtgba_sat_minimize().
      * src/tgbatest/ltl2tgba.cc: Adjust calls to
      dtba_sat_minimize().
      * src/tgbatest/satmin.test: Adjust calls.
      bcd794c6
    • Alexandre Duret-Lutz's avatar
      ltlcross: Complement deterministic automata. · 1029d08a
      Alexandre Duret-Lutz authored
      * src/bin/ltlcross.cc: Complement deterministic automata,
      and use them for additional intersection checks.
      * NEWS, doc/org/ltlcross.org, src/bin/man/ltlcross.x: Document it.
      1029d08a
    • Alexandre Duret-Lutz's avatar
      minimize_obligation: can complement the input TGBA if deterministic · 2dda2c91
      Alexandre Duret-Lutz authored
      This makes dstar2tgba able to produce a minimal WDBA when the input DRA
      represent an obligation property.
      
      * src/tgbaalgos/minimize.cc (minimize_obligation): When the
      formula is not supplied but the input automaton is deterministic,
      complement it to check the result of WDBA minimization.
      * src/tgbatest/ltl2dstar.test, src/tgbatest/ltl2dstar2.test: Improve
      tests.
      2dda2c91
    • Alexandre Duret-Lutz's avatar
      satsolver: new function · 3b10bb3b
      Alexandre Duret-Lutz authored
      Uses the value of the SPOT_SATSOLVER environment variable
      to decide how to call the SAT solver.
      
      * src/misc/satsolver.cc, src/misc/satsolver.hh: New files.
      * src/misc/Makefile.am: Add them.
      * src/tgbaalgos/dtbasat.cc, src/tgbaalgos/dtgbasat.cc: Use satsolver().
      3b10bb3b
    • Alexandre Duret-Lutz's avatar
      Implement dtgba_sat_minimize(). · 679df4ee
      Alexandre Duret-Lutz authored
      Joint work with Soheib Baarir.
      
      * src/tgbaalgos/dtgbasat.cc, src/tgbaalgos/dtgbasat.hh: New files.
      * src/tgbaalgos/Makefile.am: Add them.
      * src/tgbaalgos/postproc.cc, src/tgbaalgos/postproc.hh: Add
      a dtgba-sat-minimize option.
      * src/tgbatest/ltl2tgba.cc: Add option -RG.
      * src/tgbatest/satmin.test: Add more tests.
      679df4ee
    • Alexandre Duret-Lutz's avatar
    • Alexandre Duret-Lutz's avatar
      Add some test of the SAT-based minimization. · 84dabae3
      Alexandre Duret-Lutz authored
      * src/tgbatest/satmin.test: New file.
      * src/tgbatest/Makefile.am: Add it.
      84dabae3
    • Alexandre Duret-Lutz's avatar
      postproc: Add a sat-minimize option. · b679adad
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/postproc.hh, src/tgbaalgos/postproc.cc: Here.
      b679adad
    • Alexandre Duret-Lutz's avatar
      dtbasat: implement dba_sat_minimize() · d9f3ca71
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/dtbasat.cc, src/tgbaalgos/dtbasat.hh: New files.
      * src/tgbaalgos/Makefile.am: Add them.
      * src/tgbatest/ltl2tgba.cc: Add option -RS.
      d9f3ca71
    • Alexandre Duret-Lutz's avatar
      complete: new algorithm for TGBAs · 3fd49da1
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/complete.cc, src/tgbaalgos/complete.hh: New files.
      * src/tgbaalgos/Makefile.am: Add them.
      3fd49da1
    • Alexandre Duret-Lutz's avatar
      dbacomp: connect only back-links and generalize to tgba · 78e76eb0
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/dbacomp.cc: Here.
      * src/tgbaalgos/dbacomp.hh: Adjust documentation.
      * src/tgbatest/dbacomp.test: New file.
      * src/tgbatest/Makefile.am (TESTS): Add it.
      * src/tgbatest/det.test: Update.
      78e76eb0
    • Alexandre Duret-Lutz's avatar
      tba_determinize: add a cycle_threshold · 63b7cdb6
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/powerset.cc, src/tgbaalgos/powerset.hh
      (tba_determinize, tba_determinize_check): Add a cycle_threshold
      argument.
      * src/tgbaalgos/postproc.cc: Use it.
      * src/tgbatest/ltl2tgba.cc: Adjust calls.
      63b7cdb6
    • Alexandre Duret-Lutz's avatar
      postproc: use tba_determinize_check() · 0117fc2c
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/postproc.cc: Use tba_determinize_check()
      if option "tba-det" is set.
      * src/tgbaalgos/postproc.hh (tba_determinize_): New attribute.
      * src/tgbatest/det.test: New file.
      * src/tgbatest/Makefile.am (TESTS): Add it.
      0117fc2c
    • Alexandre Duret-Lutz's avatar
      dba_determinize: Add a threshold argument. · 07ab225c
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/powerset.cc, src/tgbaalgos/powerset.hh
      (dba_determinize, dba_determinize_check): Add a threshold
      argument.
      * src/tgbatest/ltl2tgba.cc (-O, -RQ): Accept a threshold
      argument.
      07ab225c
    • Alexandre Duret-Lutz's avatar
      Implement tba_determinize_check(), following Dax et al. (ATVA'07). · 4ac6468b
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/powerset.cc, src/tgbaalgos/powerset.hh
      (tba_determinize_check): New function.
      * src/tgbatest/ltl2tgba.cc (-O): Use it.
      4ac6468b
    • Alexandre Duret-Lutz's avatar
      Introduce a dba_complement() function. · bd2e78c1
      Alexandre Duret-Lutz authored
      Loosely based on "Complementing Deterministic Büchi Automata in
      Polynomial Time", R. P. Kurshan, 1987, J. Comp. Syst. Sci. 35.
      
      * src/tgbaalgos/dbacomp.cc, src/tgbaalgos/dbacomp.hh: New files.
      * src/tgbaalgos/Makefile.am: Add them.
      * src/tgbatest/ltl2tgba.cc (-DC): New option to test it.
      bd2e78c1
    • Alexandre Duret-Lutz's avatar
      Implementent tba_determinize(), based on Dax et al (ATVA'07). · ec5bbf4f
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/powerset.hh,
      src/tgbaalgos/powerset.cc (tba_determinize): New function.
      * src/tgbatest/ltl2tgba.cc (-RQ): New option, for testing.
      ec5bbf4f
    • Alexandre Duret-Lutz's avatar
      reachiter: fix the DFS, and add a version with on_stack() · 29bc087d
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/reachiter.hh, src/tgbaalgos/reachiter.cc: Fix the
      tgba_reachable_iterator_depth_first implementation by not making
      inheriting from tgba_reachable_iterator.  Add a
      tgba_reachable_iterator_depth_first_stack
      * src/tgbatest/sim.test, src/tgbatest/dstar.test: Adjust.
      29bc087d
    • Alexandre Duret-Lutz's avatar
      ltlcross: Allow %D, %N, or %T to be used multiple time · 57f712fc
      Alexandre Duret-Lutz authored
      For example to interface with Rabinizer, we can now use
      'java -jar /pathto/Rabinizer.jar -ltl2dstar %F %D; mv %D.dst %D'
      because Rabinizer always append a suffix to its last argument, we
      rename the file...
      
      * src/bin/ltlcross.cc (printable_result_filename): Adjust.
      57f712fc
    • Alexandre Duret-Lutz's avatar
      d561dfb7
    • Alexandre Duret-Lutz's avatar
      dstar: Improve conversion from DRA to BA. · d7027c34
      Alexandre Duret-Lutz authored
      Extended former conversion from DRA->DBA to handle
      the case where some SCC is not DBA-realizable.
      
      * src/dstarparse/dra2dba.cc: Rename as...
      * src/dstarparse/dra2ba.cc: ... this.
      (dra_to_dba, dra_to_dba_worker): Rename as...
      (dra_to_ba, dra_to_ba_worker): ... these and extend.
      * src/dstarparse/Makefile.am, src/dstarparse/public.hh,
      src/dstarparse/dstar2tgba.cc, src/dstarparse/nra2nba.cc: Adjust.
      * NEWS: Update the description of dstar2tgba accordingly.
      d7027c34
  3. 23 Aug, 2013 10 commits
    • Alexandre Duret-Lutz's avatar
    • Alexandre Duret-Lutz's avatar
      dstar2tgba: new command. · d3b81809
      Alexandre Duret-Lutz authored
      * src/bin/dstar2tgba.cc, src/bin/man/dstar2tgba.x: New files.
      * src/bin/Makefile.am, src/bin/man/Makefile.am: Add them.
      * NEWS: Mention it.
      * src/bin/ltl2tgba.cc, src/tgbaalgos/stats.cc, doc/org/ltl2tgba.org:
      Rename the %S sequence as %c, for consistency with dstar2tgba.
      * src/tgbatest/ltl2dstar.test: Add more tests.
      * src/tgbatest/ltl2dstar2.test: New file.
      * src/tgbatest/Makefile.am: Add it.
      d3b81809
    • Alexandre Duret-Lutz's avatar
      dstar: implement dra_to_dba() · 9a7590a6
      Alexandre Duret-Lutz authored
      This is an implementation of Krishnan's ISAAC'94 paper to convert
      deterministic Rabin automata into DBA when possible.
      
      * src/dstarparse/dra2dba.cc: New file.
      * src/dstarparse/dstar2tgba.cc: New file.
      * src/dstarparse/Makefile.am: Add them.
      * src/dstarparse/nra2nba.cc (nra_to_nba): Adjust so
      that dra_to_dba() can call it using a masked automaton.
      * src/dstarparse/public.hh (dra_to_dba, dstar_to_tgba): Declare.
      * src/tgbatest/ltl2tgba.cc: Add an -XDD option.
      * src/tgbatest/dstar.test: More tests.
      9a7590a6
    • Alexandre Duret-Lutz's avatar
      Introduce some masked tgba. · ce0aec60
      Alexandre Duret-Lutz authored
      * src/tgba/tgbamask.cc, src/tgba/tgbamask.hh,
      src/tgba/tgbaproxy.cc, src/tgba/tgbaproxy.hh: New files.
      * src/tgba/Makefile.am: Add them.
      * src/tgbatest/explicit3.cc, src/tgbatest/explicit3.test:
      New files.
      * src/tgbatest/Makefile.am: Add them.
      ce0aec60
    • Alexandre Duret-Lutz's avatar
      Introduce spot::state_set. · 68ce9980
      Alexandre Duret-Lutz authored
      * src/tgba/state.hh: Define state_set and shared_state_set.
      * src/tgba/taatgba.cc, src/tgba/taatgba.hh: Rename the existing
      state_set (that inherits from spot::state) as set_state.
      * src/tgba/tgbakvcomplement.cc: Use shared_state_set instead
      of state_set.
      * src/tgbaalgos/minimize.cc (state_set): Rename as...
      (build_state_set): ... this.
      68ce9980
    • Alexandre Duret-Lutz's avatar
    • Alexandre Duret-Lutz's avatar
      ltlcross: add support for ltl2dstar's output. · 337aeefc
      Alexandre Duret-Lutz authored
      * src/bin/ltlcross.cc: Add support for %D.
      * src/bin/man/ltlcross.x: Add example.
      * NEWS: Mention it.
      * src/tgbatest/ltl2dstar.test: New file.
      * src/tgbatest/Makefile.am: Add it.
      337aeefc
    • Alexandre Duret-Lutz's avatar
      dstarparse: Preliminary work on a parser for ltl2dstar. · 2da0053c
      Alexandre Duret-Lutz authored
      Supports reading Rabin and Streett automata, and converting them to
      nondeterministic Büchi automata (for Rabin) or TGBA (for Streett).
      
      * src/dstarparse/Makefile.am, src/dstarparse/dstarparse.yy,
      src/dstarparse/dstarscan.ll, src/dstarparse/fmterror.cc,
      src/dstarparse/parsedecl.hh, src/dstarparse/public.hh,
      src/dstarparse/nra2nba.cc, src/dstarparse/nsa2tgba.cc: New files.
      * configure.ac, src/Makefile.am, README: Adjust.
      * src/tgbatest/ltl2tgba.cc: Add options -XD, -XDB.
      * src/tgbatest/dstar.test: New file.
      * src/tgbatest/Makefile.am (TESTS): Add it.
      2da0053c
    • Alexandre Duret-Lutz's avatar
      bitvect: implement a dynamic bit-vector class. · 5a3b1a99
      Alexandre Duret-Lutz authored
      * src/misc/bitvect.cc, src/misc/bitvect.hh: New files.
      * src/misc/Makefile.am: Add them.
      * src/tgbatest/bitvect.cc, src/tgbatest/bitvect.test: New files.
      * src/tgbatest/Makefile.am: Add them.
      5a3b1a99
    • Alexandre Duret-Lutz's avatar
      degen: Improve when initial state is accepting without self-loop. · dfc5ff95
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/degen.cc: Choose the initial level according
      to acceptance condition common to all outgoing transitions.
      * src/tgbatest/degenid.test: Add test case.
      * NEWS: Mention it.
      dfc5ff95
  4. 29 Jul, 2013 4 commits