1. 28 Apr, 2012 40 commits
    • Alexandre Duret-Lutz's avatar
      Generalize syntactic implication for event. and univ. formulae. · 2f036493
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (syntactic_implication_aux): Refine
      rules to deal with pure eventualities and purely universal
      properties.
      * src/ltltest/reduccmp.test: Add tests.
      2f036493
    • Alexandre Duret-Lutz's avatar
      Translate Boolean formulae as BDD using the ltl_simplifier cache. · 07e40e70
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.hh, src/ltlvisit/simplify.cc
      (ltl_simplifier::ltl_simplifier, ltl_simplifier::get_dict): Make
      it possible to supply and retrieve the dictionary used.
      (ltl_simplifier::as_bdd): New function, exported from the cache.
      * src/tgbaalgos/ltl2tgba_fm.cc (translate_dict): Store the
      ltl_simplifier object.
      (translate_dict::boolean_to_bdd): Call ltl_simplifier::as_bdd.
      (translate_ratexp): New wrapper around the ratexp_trad_visitor,
      calling boolean_to_bdd whenever possible.
      (ratexp_trad_visitor): Do not deal with negated formulae, there
      are necessarily Boolean and handled by translate_ratexp().
      (ltl_visitor): Adjust to call translate_ratexp.
      (ltl_to_tgba_fm): Adjust passing of the ltl_simplifier to the
      translate_dict, and make sure everybody is using the same
      dictionary.
      * src/tgbatest/ltl2tgba.cc: Pass the dictionary to the
      ltl_simplifier.
      07e40e70
    • Alexandre Duret-Lutz's avatar
      Rewrite syntactic implication using a single function. · 369ad87e
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (inf_left_recurse_visitor,
      inf_right_recurse_visitor): Remove.
      (syntactic_implication, syntactic_implication_aux): Rewrite all
      rules for syntactic implication.
      (syntactic_implication_neg): Simplify.
      369ad87e
    • Alexandre Duret-Lutz's avatar
      Decrease the maximum bound used in random BUnOps. · 7514cc15
      Alexandre Duret-Lutz authored
      * src/ltlvisit/randomltl.cc (bunop_bounded_builder,
      bunop_bool_bounded_builder): Set the maximum value
      to 3 instead of 4, to speed up the test suite.
      7514cc15
    • Alexandre Duret-Lutz's avatar
      Avoid containment checks on equal formulae. · c54627be
      Alexandre Duret-Lutz authored
      * src/ltlvisit/contain.cc
      (language_containment_checker::contained,
      language_containment_checker::neg_contained,
      language_containment_checker::contained_neg): Detect
      cases where both formulae are equal.
      c54627be
    • Alexandre Duret-Lutz's avatar
      Check that reductions are legitimates with containment. · 7f7627bf
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc, src/ltlvisit/simplify.hh
      (are_equivalent): Export this function from the cache.
      * src/ltltest/reduc.cc, src/ltltest/equals.cc: Use
      are_equivalent() to check that the reductions are legitimate.
      7f7627bf
    • Alexandre Duret-Lutz's avatar
      Compare Boolean LTL formulae using BDDs. · c9a659c8
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (syntactic_implication): Here.
      c9a659c8
    • Alexandre Duret-Lutz's avatar
      Merge the syntactic implication code with ltl_simplifier. · fea49630
      Alexandre Duret-Lutz authored
      So that we can latter use some combined optimizations.
      
      * src/ltlvisit/simplify.hh, src/ltlvisit/simplify.cc: Integrate
      the code from syntimpl.cc
      * src/ltlvisit/syntimpl.hh, src/ltlvisit/syntimpl.cc: Delete.  All
      code has been moved above.
      * src/ltlvisit/Makefile.am: Adjust.
      * src/ltltest/syntimpl.cc: Adjust code.
      fea49630
    • Alexandre Duret-Lutz's avatar
      3db13a6f
    • Alexandre Duret-Lutz's avatar
      Rewrite xor, =>, and <=> in negative_normal_form(). · 03fd46a1
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.hh, src/ltlvisit/simplify.cc
      (ltl_simplify::negative_normal_form): Remove the third
      parameter and always rewrite XOR, =>, and <=>.  This avoid
      problems with the cache, that could have been populated with
      a different value for this third parameter.
      * src/ltltest/reduc.cc, src/tgbaalgos/ltl2tgba_fm.cc: Adjust
      calls to negative_normal_form().
      * src/ltltest/nenoform.test: Adjust tests.
      03fd46a1
    • Alexandre Duret-Lutz's avatar
      Mark reduce_tau03() as deprecated. · b89f86ed
      Alexandre Duret-Lutz authored
      * src/ltlvisit/contain.hh (reduce_tau03): Mark as deprecated.
      * src/tgbaalgos/ltl2tgba_fm.cc, src/tgbatest/ltl2tgba.cc,
      src/ltltest/equals.cc: Do not include ltlvisit/contain.hh, since
      it's not used.
      b89f86ed
    • Alexandre Duret-Lutz's avatar
      Remove basicreduce files. ltl_simplifier does all the work. · 5c1729d6
      Alexandre Duret-Lutz authored
      * src/ltlvisit/basicreduce.cc, src/ltlvisit/basicreduce.hh: Delete.
      * src/ltlvisit/Makefile.am: Remove them.
      5c1729d6
    • Alexandre Duret-Lutz's avatar
      Deprecate reduce() in favor of ltl_simplifier. · 67f4e8b5
      Alexandre Duret-Lutz authored
      * src/ltlvisit/reduce.hh: Mark the file as obsolete.
      (reduce): Declare this function as obsolete.
      * src/ltlvisit/reduce.cc: Define SKIP_DEPRECATED_WARNING
      so we can include reduce.hh.
      * src/sanity/includes.test: Also use SKIP_DEPRECATED_WARNING
      when compiling headers.
      * iface/dve2/dve2check.cc,
      src/ltltest/equals.cc, src/ltltest/randltl.cc,
      src/ltltest/reduc.cc, src/tgbaalgos/ltl2tgba_fm.hh,
      src/tgbaalgos/ltl2tgba_fm.cc, src/tgbatest/randtgba.cc,
      wrap/python/ajax/spot.in, wrap/python/spot.i: Adjust
      to use ltl_simplifier.
      * src/tgbatest/ltl2tgba.cc: Adjust to use ltl_simplifier,
      and replace -fr1...-fr7 options by a single -fr option.
      * src/tgbatest/spotlbtt.test: Adjust -fr flags accordingly.
      * src/tgbatest/reductgba.cc: Do not include reduce.hh.
      67f4e8b5
    • Alexandre Duret-Lutz's avatar
      Move the remaining reduce() logic into ltl_simplifier. · c0085a8f
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.hh
      (ltl_simplifier::negative_normal_form): Allow logical
      unabbreviations during the NNF pass.
      * src/ltlvisit/simplify.cc
      (ltl_simplifier::negative_normal_form)
      (negative_normal_form_visitor): Adjust.
      (ltl_simplifier::simplify): Request unabbreviations.
      * src/ltlvisit/reduce.cc (reduce): Remove most
      of the code, leaving only a call ltl_simplifier
      and some wrapper code to convert options.
      * src/ltltest/reduccmp.test: Add more test cases.
      c0085a8f
    • Alexandre Duret-Lutz's avatar
      Typo in the code rewriting "a M 1 = Fa". · d4d4c0e7
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (simplify_visitor): Fix it,
      and leave the trace code.
      d4d4c0e7
    • Alexandre Duret-Lutz's avatar
      Remove the negative_normal_form call from reduce(). · c2335edb
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (ltl_simplifier::simplify):
      Convert in negative normal form if needed.
      * src/ltlvisit/reduce.cc (reduce): Do not call
      negative_normal_form().
      c2335edb
    • Alexandre Duret-Lutz's avatar
      Move language containment into ltl_simplifier. · 1087c623
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc: Integrate the tau03
      containment rules.
      * src/ltlvisit/simplify.hh: Add options to select simplifications.
      * src/ltlvisit/reduce.cc (reduce): Do not call reduce_tau03().
      * src/ltlvisit/contain.cc (reduce_tau03_visitor): Remove.
      (reduce_tau03): Implement it using ltl_simplifier.
      1087c623
    • Alexandre Duret-Lutz's avatar
      Generalize G,&,| rewritings to deal with event. and univ. terms. · 82b42494
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (ltl_simplifier): Adjust
      code.
      * src/ltltest/reduccmp.test: Add some test cases.
      82b42494
    • Alexandre Duret-Lutz's avatar
      More rewritings or multop::And and multop::Or. · ab7a1c7a
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (ltl_simplifier): Add more rewritings
      for formulae that are both universal and eventual.
      * src/ltltest/reduccmp.test: Add six more cases.
      ab7a1c7a
    • Alexandre Duret-Lutz's avatar
      47fb4491
    • Alexandre Duret-Lutz's avatar
      Fix a case caught by the random formula generator. · ca686cb0
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (ltl_simplifier): Since we are processing
      the formula bottom-up, don't assume all trivial simplification have
      been done.
      * src/ltltest/reduccmp.test: More tests.
      ca686cb0
    • Alexandre Duret-Lutz's avatar
      Reimplement basic_reduce()'s rules in ltl_simplifier. · ca2fe4f3
      Alexandre Duret-Lutz authored
      So far I have only checked these rewritings with reduccmp.test.
      There are probably a few kinks to iron out.
      
      * src/ltlvisit/simplify.cc: Reimplement most of the basic
      rewriting rules, leaving some FIXME comments for dubious ones.
      * src/ltlast/multop.cc, src/ltlast/multop.hh: Ignore NULL
      pointers in the vector.
      * src/ltlvisit/reduce.cc (reduce): Do not call basic_reduce().
      * src/ltltest/reduccmp.test: Adjust tests.
      ca2fe4f3
    • Alexandre Duret-Lutz's avatar
    • Alexandre Duret-Lutz's avatar
      event./univ. and syntactic implications rewriting in ltl_simplifier. · dd1cd89a
      Alexandre Duret-Lutz authored
      * src/ltlvisit/reduce.cc (reduce_visitor): Move ...
      * src/ltlvisit/simplify.cc (simplify_visitor): ... here, and
      adjust to use the new ltl_simplifier_options.
      * src/ltlvisit/reduce.cc (reduce): Use ltl_simplifier
      to perform the work of reduce_visitor.  Eventually we want to
      get rid of reduce.cc.
      * src/ltlvisit/reduce.hh (reduce): Remove the
      syntactic_implication_cache used as third argument.
      dd1cd89a
    • Alexandre Duret-Lutz's avatar
      Take trivial identities into account to simplify basicreduce. · aa5c2f60
      Alexandre Duret-Lutz authored
      * src/ltlvisit/basicreduce.cc: Do not test
      for things like X(true), F(false), or `a U 1`.
      These are all trivial identities.
      aa5c2f60
    • Alexandre Duret-Lutz's avatar
      Introduce ltl_simplifier. · 9f7ef5d0
      Alexandre Duret-Lutz authored
      It is limited to negative_normal_form_visitor for now.
      
      * src/ltlvisit/simplify.cc, src/ltlvisit/simplify.hh: New files.
      * src/ltlvisit/Makefile.am: Add them.
      * src/ltlvisit/nenoform.cc, src/ltlvisit/nenoform.hh: Rewrite
      using ltl_simplifier.
      9f7ef5d0
    • Alexandre Duret-Lutz's avatar
      Cosmetic change to please sanity checks. · 0e4e2a79
      Alexandre Duret-Lutz authored
      * src/ltlvisit/randomltl.cc (random_formula::update_sums): Remove
      duplicate semicolon.
      0e4e2a79
    • Alexandre Duret-Lutz's avatar
      Disable LTL reductions on SERE formulae. · 6e6b6b1e
      Alexandre Duret-Lutz authored
      * src/ltlvisit/contain.cc (recurse, reduce_tau03): Do not
      run on non-PSL formulae.
      * src/ltlvisit/reduce.cc (reduce_visitor::visit): Skip
      multop::Fusion operators, and do not run syntactic_implication_neg
      on SERE formulae.
      * src/ltlvisit/syntimpl.cc (inf_right_recurse_visitor::visit):
      Skip [*0].
      6e6b6b1e
    • Alexandre Duret-Lutz's avatar
      Add support for the {SERE}! PSL operator. · fdd73d51
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlscan.ll: Recognize }!.  Also remove
      five duplicate rules.
      * src/ltlparse/ltlparse.yy: Build {r}<>->1 when parsing {r}!.
      * src/ltlvisit/tostring.cc: Print {r}! instead of {r}<>->1.
      * src/ltltest/tostring.test, src/ltltest/equals.test:
      Add more tests.
      fdd73d51
    • Alexandre Duret-Lutz's avatar
      Fix handling of PSL operators in reductions rules. · c8801935
      Alexandre Duret-Lutz authored
      We still don't have any PSL-specific reductions, but at least
      the LTL reduction now appear to work on PSL formulas.
      
      * src/ltlvisit/basicreduce.cc (basic_reduce_visitor): Fix the
      call to std::copy to handle Concat, Fusion, and AndNLM.
      * src/ltlvisit/reduce.cc (reduce_visitor): Fix handling
      of UConcat, EConcat, and EConcatMarked.
      * src/tgbatest/randpsl.test: Activate reductions.
      * src/ltltest/reducpsl.test: New file.
      * src/ltltest/Makefile.am (TESTS): Add it.
      c8801935
    • Alexandre Duret-Lutz's avatar
      Plug a memory leak in randltl. · b8b4aa72
      Alexandre Duret-Lutz authored
      * src/ltlvisit/randomltl.hh (random_formula::~random_formula):
      Declare as virtual.
      b8b4aa72
    • Alexandre Duret-Lutz's avatar
      Add random generators of Boolean, SERE, and PSL formula. · cce6dd34
      Alexandre Duret-Lutz authored
      * src/ltlvisit/randomltl.cc, src/ltlvisit/randomltl.hh:
      (random_boolean, random_sere, random_psl): Add new classes.
      * src/ltltest/randltl.cc: Add options to support the above.
      Nore: the -p option was renamed to -pL for consistency, but
      it is still understood.
      cce6dd34
    • Alexandre Duret-Lutz's avatar
      Make it possible to format SERE. · cc889a7f
      Alexandre Duret-Lutz authored
      * src/ltlvisit/tostring.hh, src/ltlvisit/tostring.cc (to_string):
      Add third option to enable formating suitable for SERE.
      cc889a7f
    • Alexandre Duret-Lutz's avatar
    • Alexandre Duret-Lutz's avatar
      Prepare the introduction of random_sere() and random_psl(). · 7c7704f9
      Alexandre Duret-Lutz authored
      * src/ltlvisit/randomltl.hh (random_ltl): Split this class into...
      (random_formula, random_ltl): ... these.
      * src/ltlvisit/randomltl.cc: New
      7c7704f9
    • Alexandre Duret-Lutz's avatar
      Speedup syntactic_implication() by using a cache. · 4ef7805e
      Alexandre Duret-Lutz authored
      * src/ltlvisit/syntimpl.hh (syntactic_implication,
      syntactic_implication_neg): Move as member of ...
      (syntactic_implication_cache): ... this new class, that holds
      a cache of results to speedup these functions.
      * src/ltlvisit/syntimpl.cc: Adjust to use (lookup, populate,
      and cleanup) the cache.
      * src/ltltest/syntimpl.cc: Likewise.
      * src/ltlvisit/reduce.hh (reduce): Take an optional
      syntactic_implication_cache parameter.
      * src/ltlvisit/reduce.cc: Adjust to use a
      syntactic_implication_cache.
      * src/ltltest/equals.cc: Call dump_instances() to help debugging.
      4ef7805e
    • Alexandre Duret-Lutz's avatar
      Speedup some rewriting by detecting cases where they do nothing. · 20c088a4
      Alexandre Duret-Lutz authored
      * src/ltlvisit/nenoform.cc, src/ltlvisit/lunabbrev.cc,
      src/ltlvisit/simpfg.cc, src/ltlvisit/tunabbrev.cc: Do not recurse
      if the formula properties indicate that it is already in the right
      form.
      20c088a4
    • Alexandre Duret-Lutz's avatar
      Remove the has_mark() function in favor of the is_marked() method. · 6380968f
      Alexandre Duret-Lutz authored
      * src/ltlast/unop.cc (NegClosure): Reset is.not_marked.
      * src/ltlvisit/mark.hh,
      src/ltlvisit/mark.cc (has_mark_visitor, has_mark): Remove.
      * src/tgbaalgos/ltl2tgba_fm.cc: Use f->is_marked() instead
      of has_mark(f).
      6380968f
    • Alexandre Duret-Lutz's avatar
      Get rid of all dynamic_cast<>s while working on LTL formulae. · 957ba664
      Alexandre Duret-Lutz authored
      They are too slow.
      
      * src/ltlast/formula.hh (opkind, kind, kind_): Use an enum
      to indicate the actual kind of the formula.  This way we can
      check the kind of a formula without relying on dynamic_cast.
      * src/ltlast/atomic_prop.cc, src/ltlast/automatop.cc,
      src/ltlast/binop.cc, src/ltlast/bunop.cc, src/ltlast/constant.cc,
      src/ltlast/multop.cc, src/ltlast/refformula.cc,
      src/ltlast/refformula.hh, src/ltlast/unop.cc: Adjust constructors.
      * src/ltlvisit/basicreduce.cc, src/ltlvisit/mark.cc,
      src/ltlvisit/reduce.cc, src/ltlvisit/syntimpl.cc,
      src/ltlvisit/tostring.cc: Replace all dynamic_cast by a
      call to kind() followed by a static_cast.
      957ba664
    • Alexandre Duret-Lutz's avatar
      Replace the constant_term visitor by a flag in the formulae. · 48cde88b
      Alexandre Duret-Lutz authored
      * src/ltlast/formula.hh (formula::accepts_eword): New method.
      (formula::is.accepting_eword): New flag.
      * src/ltlast/formula.cc (print_formula_props): Display the new
      property.
      * src/ltlast/atomic_prop.cc, src/ltlast/automatop.cc,
      src/ltlast/binop.cc, src/ltlast/bunop.cc, src/ltlast/constant.cc,
      src/ltlast/multop.cc, src/ltlast/unop.cc: Update
      is.accepting_eword as appropriate.
      * src/ltltest/consterm.cc, src/tgbaalgos/ltl2tgba_fm.cc: Adjust to
      use accepts_eword().
      * src/ltlvisit/consterm.cc, src/ltlvisit/consterm.hh: Delete.
      * src/ltlvisit/Makefile.am: Remove these files.
      48cde88b