1. 28 Apr, 2012 40 commits
    • 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
      * src/tgbatest/ltl2tgba.cc: Pass the dictionary to the
    • 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.
    • 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.
    • Alexandre Duret-Lutz's avatar
      Avoid containment checks on equal formulae. · c54627be
      Alexandre Duret-Lutz authored
      * src/ltlvisit/contain.cc
      language_containment_checker::contained_neg): Detect
      cases where both formulae are equal.
    • Alexandre Duret-Lutz's avatar
      Fix translation of '{(c&!c)[->0..1]}!'. · 58bbaa08
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/ltl2tgba_fm.cc (ratexp_trad_visitor::visit): Fix
      the translation of the Goto operator.
      (ratexp_trad_visitor::next_to_concat): More comments.
      * src/ltltest/reduccmp.test: Add a test case.
    • Alexandre Duret-Lutz's avatar
      Fix a Clang-2.9 warning. · 1507dbc6
      Alexandre Duret-Lutz authored
      * src/tgbaalgos/ltl2tgba_fm.cc (trace_ltl_bdd):
      Declare as unused.
    • 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.
    • Alexandre Duret-Lutz's avatar
      Fix universal and eventual rules for M and W. · cd9369c1
      Alexandre Duret-Lutz authored
      * src/ltlast/binop.cc: a M b is eventual if both a and b are
      eventual, or if b == 1.  a W b is universal if both a and b
      are universal or if b == 0.
      * src/ltltest/kind.test: New test case.
    • Alexandre Duret-Lutz's avatar
      Compare Boolean LTL formulae using BDDs. · c9a659c8
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (syntactic_implication): Here.
    • 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.
    • Alexandre Duret-Lutz's avatar
    • 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.
    • 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.
    • 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.
    • 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.
    • 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
      (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.
    • 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.
    • 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
    • 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.
    • 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
      * src/ltltest/reduccmp.test: Add some test cases.
    • 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.
    • Alexandre Duret-Lutz's avatar
      Make sure 'a U XXXFb' reduces to 'XXXFb'. Spot 0.7.1 missed that. · 09d96969
      Alexandre Duret-Lutz authored
      * src/ltltest/reduccmp.test: Add the test.
    • Alexandre Duret-Lutz's avatar
    • 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.
    • 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.
    • 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.
    • Alexandre Duret-Lutz's avatar
      Adjust kind.test Adjust after the change of 2011-05-23. · 503bdb5b
      Alexandre Duret-Lutz authored
      * src/ltltest/kind.test: More pure eventualities and purely
      universal properties are detected.
    • 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.
    • Alexandre Duret-Lutz's avatar
    • Alexandre Duret-Lutz's avatar
      Generalize computation of is.eventual and is.universal. · 8ecf57e8
      Alexandre Duret-Lutz authored
      * src/ltlast/binop.cc (binop::binop): Generalize detection
      of pure eventualities and purely universal formulae.  E.g.
      `f U g' is a pure eventuality if g is a pure eventuality
      (regardless of f) or if g is 1.
      * src/ltlast/unop.cc (unop::unop): Compute is.eventual
      and is.universal for Not.
      * src/ltltest/kind.test: Adjust.
    • 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.
    • Alexandre Duret-Lutz's avatar
      Speedup randpsl.test. · 0caa631c
      Alexandre Duret-Lutz authored
      * src/tgbatest/randpsl.test: Run without valgrind, it is too
      slow otherwise.
    • Alexandre Duret-Lutz's avatar
      Track finite formulae. · fb386209
      Alexandre Duret-Lutz authored
      I.e., SERE without star, or LTL formula using only X and Boolean
      * src/ltlast/formula.hh, src/ltlast/formula.cc: Add a bit for
      tracking finite formulas.
      * src/ltlast/atomic_prop.cc, src/ltlast/automatop.cc,
      src/ltlast/bunop.cc, src/ltlast/constant.cc, src/ltlast/formula.cc:
      * src/ltlast/unop.cc, src/ltlast/binop.cc: Adjust and use that
      bit to refine the computation of some LTL classes.
      * src/ltltest/kind.test: New tests.
    • Alexandre Duret-Lutz's avatar
      Track syntactic classes. · df760a45
      Alexandre Duret-Lutz authored
      These are safety, guarantee, obligation, persistence, and recurrence.
      * src/ltlast/formula.hh, src/ltlast/formula.cc: Declare a bit for
      each of these classes.
      * src/ltlast/atomic_prop.cc, src/ltlast/constant.cc,
      src/ltlast/automatop.cc, src/ltlast/binop.cc, src/ltlast/bunop.cc,
      src/ltlast/unop.cc: Update these bits.
      * src/ltltest/kind.test: Update tests and add more.
    • Alexandre Duret-Lutz's avatar
      Combine Boolean formulae in Fusion arguments. · 2669df1c
      Alexandre Duret-Lutz authored
      * src/ltlast/multop.cc (multop::instance): Implement
      the rewriting.   "a:b:c[*]:d:e" becomes "{{a&&b}&c[*]}:{d&&e}".
      * src/ltlast/multop.hh: Document it.
      * src/ltltest/equals.test, src/ltltest/kind.test: Add test cases.
    • Alexandre Duret-Lutz's avatar
      Add trivial identities for &&, <>->, []-> and Boolean arguments. · a2da5184
      Alexandre Duret-Lutz authored
      * src/ltlast/binop.cc (EConcat, UConcat): Rewrite "{b}<>-> f"
      as "b && f", and rewrite "{b}[]->f" as "b->f".
      * src/ltlast/binop.hh (binop::instance): Document trivial
      identities for <>-> and []->.
      * src/ltlast/multop.cc (multop::instance): Rewrite "b1 & b2"
      as "b1 && b2" when b1 and b2 are Boolean.
      (multop::multop): Always disable is.boolean for AndNLM.
      * src/ltlast/multop.hh: Document the rewriting.
      * src/ltltest/equals.cc: Show the two formulas if the exit_code
      is 1, to help debugging.
      * src/ltltest/equals.test: Add more tests.
      * src/ltltest/kind.test: Adjust tests.
    • 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.
    • 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].
    • Alexandre Duret-Lutz's avatar
      Track SERE formulas. · 459921ef
      Alexandre Duret-Lutz authored
      * src/ltlast/atomic_prop.cc, src/ltlast/automatop.cc,
      src/ltlast/binop.cc, src/ltlast/bunop.cc, src/ltlast/constant.cc,
      src/ltlast/formula.cc, src/ltlast/formula.hh,
      src/ltlast/multop.cc, src/ltlast/unop.cc: Add a bit is.sere_formula
      to track SEREs, and fix tracking of PSL formulae.
      * src/ltltest/kind.test: Adjust.