1. 17 Dec, 2014 2 commits
    • Thibaud Michaud's avatar
      Adding function to canonicalize an automaton. · 1995602d
      Thibaud Michaud authored
      * src/tgbaalgos/are_isomorphic.cc, src/tgbaalgos/are_isomorphic.hh,
      src/bin/autfilt.cc: are_isomorphic now uses canonicalize. It returns a
      bool, because the mapping cannot be deduced easily from the
      canonicalized automaton.
      * src/graph/graph.hh: Add equality operator to trans_storage_t
      for easy comparison of transition vectors.
      * src/tgba/tgbagraph.hh: Add equality operator to tgba_graph_trans_data
      and to tgba_digraph.
      * src/tgbaalgos/canonicalize.cc, src/tgbaalgos/canonicalize.hh:
      New files.
      * src/tgbaalgos/Makefile.am: Add them.
      * src/tgbatest/isomorph.test: Test them.
      1995602d
    • Alexandre Duret-Lutz's avatar
      autfilt: --instut, --destut, --is-empty · a626a32d
      Alexandre Duret-Lutz authored
      * src/bin/autfilt.cc: Add these new options.
      * src/tgbaalgos/stutterize.cc, src/tgbaalgos/stutterize.hh: Make it
      possible to call sl() and sl2() without passing the set of atomic
      propositions.
      * src/tgbatest/stutter.test: New file.
      * src/tgbatest/Makefile.am: Add it.
      a626a32d
  2. 16 Dec, 2014 1 commit
  3. 11 Dec, 2014 1 commit
    • Alexandre Duret-Lutz's avatar
      are-isomorphic: speed it up · 541ce543
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/are_isomorphic.cc: inline is_isomorphism() into
      are_isomorphic() so that the reference vector is only sorted once,
      and both vectors are only allocated once.
      541ce543
  4. 10 Dec, 2014 6 commits
  5. 09 Dec, 2014 2 commits
    • Alexandre Duret-Lutz's avatar
      tgba: simplify usage of named properties · 61edf7f4
      Alexandre Duret-Lutz authored
      * src/tgba/tgba.hh, src/tgba/tgba.cc (set_named_prop): Add a template
      version.
      (get_named_prop): Hide the old version, and supply a template version
      that casts.
      * src/bin/ltlcross.cc, src/hoaparse/hoaparse.yy, src/tgbaalgos/hoa.cc,
      src/tgbaalgos/product.cc: Adjust usage.
      61edf7f4
    • Alexandre Duret-Lutz's avatar
      hoa: store the automaton name as a property · 5a1e38d9
      Alexandre Duret-Lutz authored
      * src/hoaparse/hoaparse.yy: Store the automaton name.
      * src/tgbaalgos/hoa.cc: Output it if it exists.
      * src/tgbatest/hoaparse.test: Adjust tests.
      5a1e38d9
  6. 08 Dec, 2014 2 commits
    • Alexandre Duret-Lutz's avatar
      hoa: mordenize printer slightly · f37ff840
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/hoa.cc: Here.
      f37ff840
    • Alexandre Duret-Lutz's avatar
      graph: let transitions() iterate only on valid transitions · fbbf584b
      Alexandre Duret-Lutz authored
      This fixes #6.
      
      * src/graph/graph.hh: Rename the old transitions() as
      transition_vector(), and implement a new transitions() that iterates
      only on non-dead transitions.
      * src/tgba/tgbagraph.hh, src/tgba/tgbagraph.cc, src/graph/ngraph.hh:
      Adjust wrappers.
      * src/hoaparse/hoaparse.yy, src/tgbaalgos/complete.cc,
      src/tgbaalgos/dtbasat.cc, src/tgbaalgos/dtgbasat.cc,
      src/tgbaalgos/randomize.cc, src/tgbaalgos/safety.cc: Adjust calls.
      fbbf584b
  7. 06 Dec, 2014 1 commit
  8. 04 Dec, 2014 2 commits
  9. 03 Dec, 2014 1 commit
    • Alexandre Duret-Lutz's avatar
      randomize: new function · c0e98912
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/randomize.cc, src/tgbaalgos/randomize.hh: New files.
      * src/tgbaalgos/Makefile.am: Add them.
      * src/graph/graph.hh (rename_states_): New method.
      * src/bin/autfilt.cc: Add options --randomize and --seed.
      * src/tgbatest/randomize.test: Test them.
      * src/tgbatest/Makefile.am: Add randomize.test.
      * NEWS: Mention randomize().
      c0e98912
  10. 02 Dec, 2014 1 commit
  11. 01 Dec, 2014 2 commits
    • Alexandre Duret-Lutz's avatar
      countstates: remove unused file · 5d8f16da
      Alexandre Duret-Lutz authored
      * src/priv/countstates.cc, src/priv/countstates.hh: Delete.
      * src/priv/Makefile.am, src/tgbaalgos/postproc.cc: Adjust.
      5d8f16da
    • Alexandre Duret-Lutz's avatar
      accconv, acccompl: remove unused files · 202b9609
      Alexandre Duret-Lutz authored
      * src/priv/acccompl.cc, src/priv/acccompl.hh,
      src/priv/accconv.cc, src/priv/accconv.hh: Delete.
      * src/priv/Makefile.am: Adjust.
      * src/tgbaalgos/ltl2tgba_fm.cc, src/tgbaalgos/scc.cc,
      src/tgbaalgos/sccinfo.cc, src/tgbaalgos/simulation.cc: Remove unused
      includes.
      202b9609
  12. 29 Nov, 2014 2 commits
    • Alexandre Duret-Lutz's avatar
      randaut: new binary · c5842c3a
      Alexandre Duret-Lutz authored
      * src/bin/randaut.cc, src/bin/man/randaut.x: New files.
      * src/bin/Makefile.am, src/bin/man/Makefile.am: Adjust.
      * src/tgbaalgos/randomgraph.hh, src/tgbaalgos/randomgraph.cc:
      Add an option to output state-based acceptance, and update
      the TGBA properties.
      * src/tgbatest/randaut.test: New test.
      * src/tgbatest/Makefile.am: Add it.
      c5842c3a
    • Thibaud Michaud's avatar
      Add documentation for is_stutter_invariant. · 6400ec85
      Thibaud Michaud authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * src/tgbaalgos/stutter_invariance.hh: Add documentation.
      6400ec85
  13. 26 Nov, 2014 1 commit
  14. 25 Nov, 2014 3 commits
  15. 20 Nov, 2014 1 commit
    • Alexandre Duret-Lutz's avatar
      monitor: add a few tests · 392c527d
      Alexandre Duret-Lutz authored
      * src/tgbatest/monitor.test: New file.
      * src/tgbatest/Makefile.am: Add it.
      * src/tgbaalgos/minimize.cc (minimize_monitor): Mark
      the output automaton as state-based.
      * src/tgba/tgbagraph.hh: Assume automata with 0 acceptance sets are also
      state-based.
      392c527d
  16. 18 Nov, 2014 1 commit
  17. 14 Nov, 2014 6 commits
    • Alexandre Duret-Lutz's avatar
      stutter check: cleanup and add test cases · f412fee6
      Alexandre Duret-Lutz authored
      * src/ltltest/ltlfilt.test: Add more tests.
      * src/ltltest/stutter.test: New test.
      * src/ltltest/Makefile.am: Adjust.
      * src/bin/ltlfilt.cc: Catch std::runtime_error.
      * src/tgba/tgbasl.hh (make_tgbasl): New function.
      * src/tgba/tgbagraph.hh (make_tgba_graph): Add another overload.
      * src/tgbaalgos/stutter_invariance.cc,
      src/tgbaalgos/stutter_invariance.hh: Take the algorithm version as an
      optional integer, and call getenv() only once.
      * bench/stutter/stutter_invariance_randomgraph.cc,
      bench/stutter/stutter_invariance_formulas.cc: Simplify using the
      above functions.
      f412fee6
    • Thibaud Michaud's avatar
      Optimizing closure and sl. · fcf6e251
      Thibaud Michaud authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * src/tgbaalgos/closure.cc, src/tgbaalgos/closure.hh: Using vectors
      instead of sets and unordered maps, adding an overload to handle rvalue
      references.
      * src/tgbaalgos/stutterize.cc, src/tgbaalgos/stutterize.hh: Adding
      an overload to handle rvalue references.
      * bench/stutter/stutter_invariance_formulas.cc,
      bench/stutter/stutter_invariance_randomgraph.cc: Automata are modified
      in-place by is_stutter_invariant so they have to be copied before being
      processed.
      * src/tgbaalgos/stutter_invariance.cc,
      src/tgbaalgos/stutter_invariance.hh: Use the in-place version of
      closure and sl.
      fcf6e251
    • Thibaud Michaud's avatar
      Remove const qualifier in translator::run return type · 5817a3c1
      Thibaud Michaud authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * src/tgbaalgos/translate.cc, src/tgbaalgos/translate.hh: Remove const
      qualifier in translator::run return type.
      5817a3c1
    • Thibaud Michaud's avatar
      Adding tgba-based stutter-invariance checking · 37bcb5d9
      Thibaud Michaud authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * src/tgbaalgos/closure.cc, src/tgbaalgos/closure.hh:
      Add closure function.
      * src/tgbaalgos/stutterize.cc, src/tgbaalgos/stutterize.hh:
      Add two implementations of "self-loopize" function.
      * src/tgbaalgos/Makefile.am: Add them.
      * src/tgba/tgbasl.cc, src/tgba/tgbasl.hh: On-the-fly implementation of
      self-loopize.
      * src/tgba/Makefile.am: Add it.
      * src/tgbatest/ltl2tgba.cc, src/tgbatest/stutter_invariant.test: Test
      closure and sl.
      * src/tgbatest/Makefile.am: Adjust.
      * src/bin/ltlfilt.cc: Modify stutter-invariant option to use
      automaton-based checking rather than syntactic-based checking.
      * src/ltlvisit/remove_x.cc, src/ltlvisit/remove_x.hh:
      Remove is_stutter_insensitive function.
      * src/tgbaalgos/stutter_invariance.cc,
      src/tgbaalgos/stutter_invariance.hh: Check if a formula is
      stutter-invariant using closure and sl.
      * wrap/python/spot.i: Add closure and sl bindings.
      * bench/stutter/stutter_invariance_formulas.cc: Generate benchmarks from
      given formulas.
      * bench/stutter/stutter_invariance_randomgraph.cc: Generate benchmarks
      from random automata.
      * bench/stutter/Makefile.am: Add them.
      * configure.ac: Add bench/stutter/Makefile.
      * bench/Makefile.am: Add stutter subdirectory.
      * README: Document bench/stutter directory.
      37bcb5d9
    • Thibaud Michaud's avatar
      random_graph: add option to generate complete deterministic automaton · c9618f91
      Thibaud Michaud authored and Alexandre Duret-Lutz's avatar Alexandre Duret-Lutz committed
      * src/tgbaalgos/randomgraph.cc, src/tgbaalgos/randomgraph.hh:
      Add option to generate a complete deterministic automaton.
      * src/tgbatest/randtgba.cc: Test it.
      c9618f91
    • Alexandre Duret-Lutz's avatar
      ltl2tgba_fm: fix non-deterministic output · 11aa708a
      Alexandre Duret-Lutz authored
      The ltl_to_tgba_fm() translation function was using a hash_map of
      maps (ugh!) to merge transitions on output.  However recent libstd++
      changed the implementation of hash_map (a.k.a. unordered_map) causing
      transitions to be output in a different order.  This
      implementation-dependent order caused the ltl2ta.test to fail because
      the BA->TA transformation can produce TA of different sizes if you
      simply change the order of transitions in the input BA! This does not
      sound like a nice property for the BA->TA transformation, but Ala Eddine
      isn't sure how to fix it yet.  In the meantime, this patch makes sure
      ltl_to_tgba_fm() will return the same output regardless of the
      implementation of hash_map.
      
      The ltl2ta.test failure has been observed with g++ 4.9.2 on Arch Linux,
      and with gcc-snapshot (5.0.0 20141016) on Debian.
      
      * src/tgbaalgos/ltl2tgba_fm.cc: Rewrite the transition merging
      using a std::vector and std::sort instead of nested maps tables.
      * src/tgbatest/ltl2ta.test: Adjust sizes to the new order.
      * NEWS: Mention the fix.
      11aa708a
  18. 13 Nov, 2014 1 commit
    • Alexandre Duret-Lutz's avatar
      ltl2tgba_fm: fix non-deterministic output · 4ea63f84
      Alexandre Duret-Lutz authored
      The ltl_to_tgba_fm() translation function was using a hash_map of
      maps (ugh!) to merge transitions on output.  However recent libstd++
      changed the implementation of hash_map (a.k.a. unordered_map) causing
      transitions to be output in a different order.  This
      implementation-dependent order caused the ltl2ta.test to fail because
      the BA->TA transformation can produce TA of different sizes if you
      simply change the order of transitions in the input BA! This does not
      sound like a nice property for the BA->TA transformation, but Ala Eddine
      isn't sure how to fix it yet.  In the meantime, this patch makes sure
      ltl_to_tgba_fm() will return the same output regardless of the
      implementation of hash_map.
      
      The ltl2ta.test failure has been observed with g++ 4.9.2 on Arch Linux,
      and with gcc-snapshot (5.0.0 20141016) on Debian.
      
      * src/tgbaalgos/ltl2tgba_fm.cc: Rewrite the transition merging
      using a std::vector and std::sort instead of nested maps tables.
      * NEWS: Mention the fix.
      4ea63f84
  19. 30 Oct, 2014 1 commit
    • Alexandre Duret-Lutz's avatar
      buddy: rename libbdd to libbddx · ad8d2422
      Alexandre Duret-Lutz authored
      * buddy/src/bdd.h, buddy/src/bvec.h, buddy/src/fdd.h: Rename as...
      * buddy/src/bddx.h, buddy/src/bvecx.h, buddy/src/fddx.h: ... these.
      * buddy/src/Makefile.am: Build libbddx.la instead of libbdd.la.
      * buddy/examples/Makefile.def: Use it.
      * Makefile.am, buddy/src/bddtest.cxx, buddy/src/bvec.c,
      buddy/src/cppext.cxx, buddy/src/fdd.c, buddy/src/imatrix.h,
      buddy/src/kernel.h, buddy/examples/adder/adder.cxx,
      buddy/examples/bddcalc/parser_.h, buddy/examples/bddtest/bddtest.cxx,
      buddy/examples/cmilner/cmilner.c, buddy/examples/fdd/fdd.cxx,
      buddy/examples/milner/milner.cxx, buddy/examples/money/money.cxx,
      buddy/examples/queen/queen.cxx, buddy/examples/solitare/solitare.cxx,
      m4/buddy.m4, src/ltlvisit/apcollect.hh, src/ltlvisit/simplify.hh,
      src/misc/bddlt.hh, src/misc/bddop.hh, src/misc/minato.hh,
      src/priv/acccompl.hh, src/priv/accconv.hh, src/priv/accmap.hh,
      src/priv/bddalloc.cc, src/tgba/bdddict.hh, src/tgba/bddprint.hh,
      src/tgba/tgbamask.hh, src/tgba/tgbasafracomplement.cc,
      src/tgbaalgos/emptiness.hh, src/tgbaalgos/gtec/sccstack.hh,
      src/tgbaalgos/neverclaim.cc, src/tgbaalgos/powerset.cc,
      src/tgbaalgos/sccfilter.hh, src/tgbaalgos/sccinfo.hh,
      src/tgbaalgos/weight.hh, wrap/python/buddy.i: Adjust.
      * NEWS, README: Document it.
      ad8d2422
  20. 28 Oct, 2014 1 commit
    • Alexandre Duret-Lutz's avatar
      tgba_digraph: add a copy constructor, and obsolete dupexp · 923785f7
      Alexandre Duret-Lutz authored
      * src/tgba/tgbagraph.hh, src/tgba/tgbagraph.cc: Add a copy constructor,
      and some method to purge unreachable states.
      * src/graph/graph.hh (defrag_states): Erase transition of removed
      states.
      * src/tgbaalgos/complete.cc, src/tgbaalgos/compsusp.cc,
      src/tgbaalgos/dtgbacomp.cc, src/tgbaalgos/simulation.cc,
      src/tgbatest/checkpsl.cc, src/tgbatest/emptchk.cc,
      src/tgbatest/ltl2tgba.cc: Adjust to use make_tgba_digraph() instead
      of tgba_dupexp_dfs() or tgba_dupexp_bfs().
      * src/tgbaalgos/dupexp.cc, src/tgbaalgos/dupexp.hh: Use
      make_tgba_digraph() when possible.
      * src/tgbatest/det.test, src/tgbatest/sim.test: Adjust expected results.
      923785f7
  21. 26 Oct, 2014 2 commits