1. 28 Apr, 2012 40 commits
    • Alexandre Duret-Lutz's avatar
      Rewrite a&XGa as Ga, and a|XFa as Fa. · 395793d9
      Alexandre Duret-Lutz authored
      The actual rules are a bit more complex:
      a & X(G(a&b...)&c...) = Ga & X(G(b...)&c...)
      a | X(Fa | c) = F(a) | c
      with the second rule being applied only if all XF can
      be removed.  See the documentation for an example.
      
      * src/ltlvisit/simplify.cc: Implement these new rules.
      * doc/tl/tl.tex: Document them.
      * src/ltltest/reduccmp.test: Add test cases.
      395793d9
    • Alexandre Duret-Lutz's avatar
      Rewrite F(a M b) as F(a & b), and G(a W b) as G(a | b). · 54d4a0a0
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc: Implement these rules.
      * src/ltltest/reduccmp.test: Add tests.
      * doc/tl/tl.tex: Document them.
      54d4a0a0
    • Alexandre Duret-Lutz's avatar
      Add implication-based rewritings from Babiak et al. (TACAS'12) · 212c7ebd
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc: Implement them here, and augment them
      to support M, and W operators.
      * src/ltltest/reduccmp.test: Add some tests.
      * doc/tl/tl.tex (Simplifications Based on Implications): Document
      these rules.
      * doc/tl/tl.bib (babiak.12.tacas): New entry.
      212c7ebd
    • Alexandre Duret-Lutz's avatar
      Add a new length_boolone() function to fix an assert in randpsl. · ed0dd0b4
      Alexandre Duret-Lutz authored
      * src/ltlvisit/length.hh (length_boolone): New function.
      * src/ltlvisit/length.cc (length_boolone): Implement it using...
      (length_boolone_visitor): ... this new visitor.
      * src/ltltest/randltl.cc: Use length_boolone() to check the result
      of the random generator, and ignore any formula larger (in
      length()) than opt_f.  This fix a bug where the random formula
      generator would sometime produce formula larger than requested,
      because of the trivial rewriting of {f}[]->e as e|!f.
      * src/ltltest/length.cc: Add option -b to call length_boolone().
      * src/ltltest/length.test: Test length_boolone().
      ed0dd0b4
    • Alexandre Duret-Lutz's avatar
      Support the PSL syntax [*1:inf], as a synonym for [*1:]. · dd527689
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlscan.ll: Parse "inf" as OP_UNBOUNDED.
      * src/ltltest/equals.test: Add some tests.
      * doc/tl/tl.tex: Document it.
      dd527689
    • Alexandre Duret-Lutz's avatar
      Replace reference to RATEXP in the parser, by reference to SERE. · fa44383e
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlparse.yy: Cleanup the names used in the grammar.
      * src/ltlparse/public.hh (parse_ratexp): Rename as...
      (parse_sere): ... this.
      * src/ltltest/consterm.cc: Adjust call to parse_ratexp().
      fa44383e
    • Alexandre Duret-Lutz's avatar
      Simplify {r1;b1}&&{r2;b2} or {b1:r1}&&{b2:r2}, or similar. · b03935a4
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc: Add four rules.
      * doc/tl/tl.tex: Document these rules.
      * src/ltltest/reduccmp.test: Add tests.
      b03935a4
    • Alexandre Duret-Lutz's avatar
      Diagnose reversed ranges like [=2..1], [->..0] or [*8..4]. · 2f9f274a
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlparse.yy: Diagnose them.
      * src/ltltest/parseerr.test: Add tests.
      2f9f274a
    • Alexandre Duret-Lutz's avatar
      Simplify {b && {r1;...;rn}}. · 614810c0
      Alexandre Duret-Lutz authored
      * doc/tl/tl.tex: Document the rules.
      * src/ltlvisit/simplify.cc (simplify_visitor): Implement them.
      * src/ltltest/reduccmp.test: Test them.
      614810c0
    • Alexandre Duret-Lutz's avatar
      Simplify {b && {r1:...:rn}} as {b && r1 && ... && rn}. · d0cfd44b
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (simplify_visitor): Do it.
      * src/ltltest/reduccmp.test: Add a test.
      * doc/tl/tl.tex: Document it.
      * src/ltlast/multop.cc: Fix the computation of is.accepting_eword
      for Fusion.  The Fusion operator never accepts [*0].
      d0cfd44b
    • Alexandre Duret-Lutz's avatar
      Simplify {b && r[*]} as {b && r}; likewise for [->] and [=]. · 77084747
      Alexandre Duret-Lutz authored
      * src/ltlvisit/simplify.cc (simplify_visitor): Do it.
      * src/ltltest/reduccmp.test: Add more tests.
      * doc/tl/tl.tex: Document it.
      77084747
    • Alexandre Duret-Lutz's avatar
      Rewrite {b}<>->f as (!b)|f instead of b->f. · f68f639e
      Alexandre Duret-Lutz authored
      * src/ltlast/binop.cc, src/ltlast/binop.hh: Here.
      * doc/tl/tl.tex, src/ltltest/equals.test: Adjust.
      f68f639e
    • Alexandre Duret-Lutz's avatar
      Add trivial identity {b}=b and !{b}=!b for any Boolean formula b. · 77d704ea
      Alexandre Duret-Lutz authored
      * src/ltlast/unop.cc: Perform the simplification.
      * src/ltlast/unop.hh, doc/tl/tl.tex: Document it.
      * src/ltltest/equals.test: Adjust test cases.
      77d704ea
    • Alexandre Duret-Lutz's avatar
      Trim DFAs used when translating PSL's closure operators. · b3cc033e
      Alexandre Duret-Lutz authored
      This fixes a bug where {(a&!a)[=2]} was translated either into an
      universal automaton (with simplification turned off) or in an
      empty automaton (with simplification turned on).
      
      * src/tgbaalgos/ltl2tgba_fm.cc (ratexp_to_dfa::translate): Trim
      the automaton.
      (ratexp_to_dfa::succ, ratexp_to_dfa::get_label): Deal with trimed
      states.
      (ltl_trad_visitor::visit(unop::Closure)): Likewise.
      * src/tgbatest/ltl2tgba.test, src/ltltest/reduccmp.test: New test
      cases.
      b3cc033e
    • 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
      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.
      58bbaa08
    • 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
      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.
      cd9369c1
    • 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
      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
      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
      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
      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.
      09d96969
    • 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
      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.
      503bdb5b
    • 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.
      8ecf57e8
    • 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
      operators.
      
      * 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:
      Adjust.
      * 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.
      fb386209
    • 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.
      df760a45
    • 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.
      2669df1c
    • 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.
      a2da5184
    • 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.
      459921ef
    • 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
      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
      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
      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