1. 10 Nov, 2009 1 commit
    • Alexandre Duret-Lutz's avatar
      Introduce tgba_explicit_labelled<label> so that we can build · 4e22bb8b
      Alexandre Duret-Lutz authored
      tgba_explicit instances labelled by other objects than strings.
      
      * src/tgba/tgbaexplicit.cc, src/tgba/tgbaexplicit.hh:
      Split tgba_explicit in two levels: tgba_explicit with unlabelled
      states, and tgba_explicit_labelled templated by the type of
      the label.  Define tgba_explicit_string (with the interface
      of the former tgba_explicit class) and tgba_explicit_formula
      for future use in ltl2tgba.cc.
      * src/tgba/tgbareduc.cc, src/tgba/tgbareduc.hh,
      src/tgbaalgos/cutscc.cc, src/tgbaalgos/dupexp.cc,
      src/tgbaalgos/emptiness.cc, src/tgbaalgos/ltl2tgba_fm.cc,
      src/tgbaalgos/powerset.cc, src/tgbaalgos/randomgraph.cc,
      src/tgbaparse/public.hh, src/tgbaparse/tgbaparse.yy,
      src/tgbatest/explicit.cc, src/tgbatest/ltl2tgba.cc: Adjust to
      use tgba_explicit_string when appropriate.
      4e22bb8b
  2. 09 Nov, 2009 12 commits
    • Alexandre Duret-Lutz's avatar
      Do not use the Boost macro from the Autoconf macro archive. · d3dcecc6
      Alexandre Duret-Lutz authored
      * m4/boost.m4: Rewrite like I already did in Vaucanson.
      d3dcecc6
    • Alexandre Duret-Lutz's avatar
      * src/tgbatest/ltlcounter.test (run): Do not run with n=12, as · 39912aa5
      Alexandre Duret-Lutz authored
      the test case might become too slow for the autobuilder.
      39912aa5
    • Alexandre Duret-Lutz's avatar
      Add a benchmark using Kristin Y. Rozier's LTLcounter scripts. · 3ce16272
      Alexandre Duret-Lutz authored
      * bench/ltlcounter/README, bench/ltlcounter/run,
      bench/ltlcounter/plot.gnu, bench/ltlcounter/defs.in,
      bench/ltlcounter/Makefile.am: New files.
      * bench/Makefile.am (SUBDIRS): Add ltlcounter.
      * configure.ac (AC_CONFIG_FILES): Adjust.
      * THANKS: Add her.
      3ce16272
    • Alexandre Duret-Lutz's avatar
      Use a timer to clock the different phases of the translation. · e539226e
      Alexandre Duret-Lutz authored
      * src/tgbatest/ltl2tgba.cc: Add option -T.
      e539226e
    • Alexandre Duret-Lutz's avatar
      Deprecate ltl::destroy(f) in favor of f->destroy() · 77df39b4
      Alexandre Duret-Lutz authored
      * src/ltlast/formula.cc, src/ltlast/formula.hh (formula::clone):
      Transform this static function into a member function.
      * src/ltlvisit/destroy.hh (destroy): Document and declare as
      deprecated.
      * bench/split-product/cutscc.cc, iface/gspn/ltlgspn.cc,
      src/eltlparse/eltlparse.yy, src/eltltest/acc.cc,
      src/evtgbaalgos/tgba2evtgba.cc, src/evtgbatest/ltl2evtgba.cc,
      src/ltlast/automatop.cc, src/ltlast/binop.cc,
      src/ltlast/multop.cc, src/ltlast/unop.cc, src/ltlenv/declenv.cc,
      src/ltlenv/declenv.hh, src/ltlparse/ltlparse.yy,
      src/ltltest/equals.cc, src/ltltest/randltl.cc,
      src/ltltest/readltl.cc, src/ltltest/reduc.cc,
      src/ltltest/syntimpl.cc, src/ltltest/tostring.cc,
      src/ltlvisit/destroy.cc src/ltlvisit/basicreduce.cc,
      src/ltlvisit/contain.cc, src/ltlvisit/reduce.cc,
      src/ltlvisit/syntimpl.cc, src/tgba/bdddict.cc,
      src/tgba/bddprint.cc, src/tgba/taa.cc,
      src/tgba/tgbabddconcretefactory.cc, src/tgba/tgbaexplicit.cc,
      src/tgba/tgbafromfile.cc, src/tgbaalgos/eltl2tgba_lacim.cc,
      src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2tgba_fm.cc,
      src/tgbaalgos/ltl2tgba_lacim.cc, src/tgbaalgos/neverclaim.cc,
      src/tgbaalgos/randomgraph.cc, src/tgbaparse/tgbaparse.yy,
      src/tgbatest/complementation.cc, src/tgbatest/eltl2tgba.cc,
      src/tgbatest/ltl2tgba.cc, src/tgbatest/ltlprod.cc,
      src/tgbatest/mixprod.cc, src/tgbatest/randtgba.cc,
      src/tgbatest/reductgba.cc, wrap/python/cgi/ltl2tgba.in,
      wrap/python/tests/ltl2tgba.py, wrap/python/tests/ltlparse.py,
      wrap/python/tests/ltlsimple.py: Adjust destroy() usage, and remove
      the #include "destroy.hh" when appropriate.
      77df39b4
    • Alexandre Duret-Lutz's avatar
      Deprecate ltl::clone(f) in favor of f->clone(). · 48fb19ea
      Alexandre Duret-Lutz authored
      * src/ltlvisit/clone.hh (clone): Document and declare as deprecated.
      * src/ltlast/formula_tree.cc, src/ltlvisit/basicreduce.cc,
      src/ltlvisit/clone.cc, src/ltlvisit/contain.cc,
      src/ltlvisit/lunabbrev.cc, src/ltlvisit/reduce.cc,
      src/ltlvisit/syntimpl.cc, src/tgba/bdddict.cc,
      src/tgba/formula2bdd.cc, src/tgba/tgbabddconcretefactory.cc,
      src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2tgba_fm.cc,
      src/tgbatest/complementation.cc, wrap/python/tests/ltlsimple.py:
      Adjust clone() usage, and remove the #include "clone.hh" when
      appropriate.
      48fb19ea
    • Alexandre Duret-Lutz's avatar
      Make it possible to clone const formulae. · e44f1b89
      Alexandre Duret-Lutz authored
      * src/ltlast/formula.hh, src/ltlast/formula.cc (clone): Declare
      as const.
      e44f1b89
    • Alexandre Duret-Lutz's avatar
      Rename formula::ref and formula::unref as formula::clone · b0888257
      Alexandre Duret-Lutz authored
      and formula::destroy.
      
      * src/ltlast/atomic_prop.cc, src/ltlast/automatop.cc,
      src/ltlast/binop.cc, src/ltlast/formula.hh, src/ltlast/formula.cc,
      src/ltlast/multop.cc, src/ltlast/unop.cc, src/ltlenv/declenv.cc,
      src/ltlvisit/basicreduce.cc, src/ltlvisit/clone.cc,
      src/ltlvisit/destroy.cc, src/ltlvisit/nenoform.cc,
      src/ltlvisit/randomltl.cc, src/ltlvisit/reduce.cc,
      src/tgbatest/randtgba.cc: Adjust.
      b0888257
    • Alexandre Duret-Lutz's avatar
      Change the way references are counted to speedup cloning. · 8e4e692e
      Alexandre Duret-Lutz authored
      Before this patch, every time you cloned a formula, the clone
      visitor would recurse into the entire AST to increment the
      reference count of all nodes.  When running ltl2tgba_fm on
      the formula generated by "LTLcounterLinear.pl 8", approx 27% of
      the time was spent in the clone visitor.
      
      After this patch, cloning a formula is just an increment of the
      reference count of the top node.  Children are decremented only
      when the top node's ref count is decremented to zero.  With this
      change, clone() and destroy() become constant time, the
      ltl2tgba_fm spend only 0.01% of the time cloning formulae.
      
      * src/ltlast/automatop.cc (~automatop): Decrement children.
      (instance): Decrement children if the instance already exists.
      * src/ltlast/binop.cc, src/ltlast/multop.cc, src/ltlast/unop.cc:
      Likewise.
      * src/ltlvisit/clone.cc (clone): Simplify, now we only need to
      call ref().
      * src/ltlvisit/destroy.cc (destroy): Simplify, now we only need
      to call unref().
      (destroy_visitor): Remove, no longer needed.
      8e4e692e
    • Alexandre Duret-Lutz's avatar
      Make it easier to debug reference counts in LTL nodes. · 631f4b5b
      Alexandre Duret-Lutz authored
      * src/ltlast/automatop.cc, src/ltlast/automatop.hh,
      src/ltlast/binop.cc, src/ltlast/binop.hh, src/ltlast/multop.cc,
      src/ltlast/multop.hh, src/ltlast/unop.cc, src/ltlast/unop.hh:
      Add a dump_instance() static method to all class.
      * src/ltltest/readltl.cc: Add option -r to dump all instances
      with their reference count, after parsing and after deletion.
      631f4b5b
    • Alexandre Duret-Lutz's avatar
      Better types for instance maps. · 3488bf45
      Alexandre Duret-Lutz authored
      * src/ltlast/unop.hh (map): Use unop* as values.
      * src/ltlast/binop.hh (map): Use binop* as values.
      * src/ltlast/multop.hh (map): Use multop* as values.
      * src/ltlast/automatop.hh (paircmp): Rename as tripletcmp.
      (map): Use automaton* as values, not formula*.
      3488bf45
    • Alexandre Duret-Lutz's avatar
      Add missing instance_count() in automatop and eltl2tgba. · f2e941cd
      Alexandre Duret-Lutz authored
      * src/ltlast/automatop.hh, src/ltlast/automatop.cc: Add missing
      instance_count() functions.
      * src/tgbatests/eltl2tgba.cc: Add missing instance_count()
      assertions at the end.
      * src/tgbatests/ltl2tgba.cc: Also call automatop::instance_count(),
      even if automatop are not used in ltl2tgba yet.  This way we won't
      forget once eltl2tgba and ltl2tgba are merged.
      f2e941cd
  3. 07 Nov, 2009 2 commits
  4. 05 Nov, 2009 2 commits
  5. 04 Nov, 2009 2 commits
  6. 03 Nov, 2009 1 commit
  7. 28 Oct, 2009 2 commits
  8. 23 Oct, 2009 1 commit
  9. 22 Oct, 2009 3 commits
    • Alexandre Duret-Lutz's avatar
      Escape labels in -KV output. · 913637a7
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/scc.cc (dump_scc_dot): Escape labels and other
      strings output between quote in dot.
      * src/tgbatest/kv.test: New file.
      * src/tgbatest/Makefile.am (TESTS): Add it.
      913637a7
    • Alexandre Duret-Lutz's avatar
      4d8239e8
    • Damien Lefortier's avatar
      Improve ltl_to_taa. · 7ce27ef9
      Damien Lefortier authored
      * src/tgba/taa.cc, src/tgba/taa.hh: taa_succ_iterator is not
      on-the-fly anymore allowing some redundant transitions to be
      removed. Also a new function to output a TAA.
      * src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2taa.hh: Add the
      refined rules from Tauriainen.
      * src/tgbatest/ltl2tgba.cc: Use -c to activate refined rules in
      ltl_to_taa.
      * src/tgbatest/spotlbtt.test: More tests.
      7ce27ef9
  10. 17 Oct, 2009 1 commit
  11. 16 Oct, 2009 3 commits
    • Damien Lefortier's avatar
      Minor fixes. · 84060b49
      Damien Lefortier authored
      * src/misc/bddop.hh, src/tgba/taa.hh, src/tgbaalgos/ltl2taa.hh:
      Fix sanity (incorrect include guard).
      * src/tgba/tgbacomplement.cc, src/tgba/tgbacomplement.hh:
      Copyright 2009.
      * src/tgbaalgos/eltl2tgba_lacim.cc: Use abbreviations.
      * src/tgbatest/taa.cc: Fix it.
      84060b49
    • Damien Lefortier's avatar
      Add a new algorithm (from Tauriainen) to translate LTL formulae to · 627b6677
      Damien Lefortier authored
      TGBA which uses TAA as an intermediate representation.  This is a
      basic version, optimizations and enhancements will come later.
      
      * src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2taa.hh: The algortihm.
      * src/tgbaalgos/Makefile.am: Adjust.
      * src/tgbatest/ltl2tgba: New option: -taa, which uses this new
      translation algorithm.
      * src/tgbatest/spotlbtt.test: Add ltl2tgba -taa.
      627b6677
    • Damien Lefortier's avatar
      Add a class to represent Transition-based Alternating Automata (TAA). · 20c1f01e
      Damien Lefortier authored
      * misc/Makefile.am, misc/bbop.cc, misc/bddop.hh: Factorize some
      code on BDDs to compute all_acceptance_conditions from
      neg_acceptance_condition.
      * src/tgba/Makefile.am, src/tgbatest/Makefile.am: Adjust.
      * src/tgba/taa.cc, src/tgba/taa.hh: The TAA class.
      * src/tgba/tgbaexplicit.hh: Use the factorized code in bddop.hh.
      * src/tgbatest/taa.cc, src/tgbatest/taa.test: Some test cases.
      20c1f01e
  12. 07 Oct, 2009 1 commit
  13. 01 Oct, 2009 7 commits
  14. 28 Sep, 2009 1 commit
  15. 18 Sep, 2009 1 commit
    • Alexandre Duret-Lutz's avatar
      Optimize previous patch. · fd0de04d
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/scc.hh (scc_map::scc::supp_rec): Initialize to
      bddfalse, since this cannot occur in reallife.
      * src/tgbaalgos/scc.cc (scc_map::update_supp_rec): Adjust.
      fd0de04d