1. 28 Apr, 2012 40 commits
    • 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
      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
      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
      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
      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
      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
      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
      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
      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
      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
      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.
    • 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.
    • 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.
    • 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.
    • 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
      * src/ltltest/equals.cc: Call dump_instances() to help debugging.
    • 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
      * 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.
    • Alexandre Duret-Lutz's avatar
      Maintain basic LTL properties using a bitfield inside formula objects. · 546260e7
      Alexandre Duret-Lutz authored
      This bitfield is easily updated as the formulae are constructed.
      Doing so avoids many AST recursions to compute these properties
      individually.  This patch removes the eventual_universal_visitor,
      as well as the kind_of() function.
      * src/ltlast/formula.hh (is_boolean, is_sugar_free_boolean,
      is_in_nenoform, is_X_free, is_sugar_free_ltl,
      is_ltl_formula, is_eltl_formula, is_psl_formula, is_eventual,
      is_universal, is_marked): New methods to query formula
      properties in constant time.
      (get_props, ltl_prop): A method and structure for
      implementation as a field bit in an unsigned, for fast
      (print_formula_props): New function.
      * src/ltlast/formula.cc (print_formula_props): Implement it.
      * src/ltlast/atomic_prop.cc, src/ltlast/binop.cc,
      src/ltlast/bunop.cc, src/ltlast/constant.cc, src/ltlast/multop.cc,
      src/ltlast/unop.cc, src/ltlast/automatop.cc: Compute the
      properties as instances are constructed.
      * src/ltlparse/ltlparse.yy: Update to use is_boolean() instead
      of kind_of().
      * src/ltltest/kind.cc: Update to use print_formula_props().
      * src/ltltest/kind.test: Adjust to test eventual and universal
      * src/ltlvisit/kind.cc, src/ltlvisit/kind.hh: Delete these files.
      * src/ltlvisit/Makefile.am: Remove kind.hh and kind.cc.
      * src/ltlvisit/reduce.cc (recurse_eu, eventual_universal_visitor):
      Remove, no longer needed.
      (reduce_visitor, is_eventual, is_universal): Adjust to
      use formula::is_eventual(), and formula::is_universal().
      * src/ltlvisit/reduce.hh (is_eventual, is_universal): Declare as
    • Alexandre Duret-Lutz's avatar
      Simplify fUf, fRf, fWf, and fRF as f. · 1671aa5d
      Alexandre Duret-Lutz authored
      * src/ltlast/binop.cc (binop::instance): Simplify fUf, fRf, fWf,
      and fRF.
      * src/ltlast/binop.hh: Document it.
      * src/ltltest/equals.test: Add new tests for 'Exp U Exp'
      and 'Exp R Exp', and all missing tests for W and M.
    • Alexandre Duret-Lutz's avatar
      Fix trivial identity (0 => Exp) == 1, and add rewritings for =>. · 473cf771
      Alexandre Duret-Lutz authored
      The new rewriting are (Exp => Exp) = 1, (Exp <=> Exp) == 1,
      and (Exp ^ Exp) == 0.
      * src/ltlast/binop.hh: Fix documentation.
      * src/ltlast/binop.cc: Fix implementation.
      * src/ltltest/equals.test: More tests.
      * src/tgbatest/emptchk.test: Remove a useless test.
    • Alexandre Duret-Lutz's avatar
      Read p=0Wq=1 and p=0Mq=1 correctly. · f2732dd8
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlscan.ll: Handle p=0Wq=1 and p=0Mq=1 in
      the same way as we did for
      * src/ltltest/parse.test: More tests.
    • Alexandre Duret-Lutz's avatar
      Accept more syntaxes as range specifications for [*], [=], and [->]. · 754ff36b
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlscan.ll (OP_SQBKT_SEP): Accept ":" and "to"
      in addition to ".." and ",".
      (OP_UNBOUNDED): Recognize "$" for the rule below.
      * src/ltlparse/ltlparse.yy: Accept [OP1:$] as a synonym
      for [OP1:], for people used to SVA's syntax.
      * src/ltltest/equals.test: Test these syntaxes.
    • Alexandre Duret-Lutz's avatar
      Introduce [->min..max] operator. · da74b4f1
      Alexandre Duret-Lutz authored
      * src/ltlast/bunop.hh: Declare bunop::Goto
      * src/ltlast/bunop.cc: Handle it.
      * src/ltlparse/ltlparse.yy,
      src/ltlparse/ltlscan.ll: Add rules for [->min..max].
      * src/tgbaalgos/ltl2tgba_fm.cc: Handle bunop::Goto in
      the translation.
      * src/ltltest/equals.test: Test trivial identities.
      * src/tgbatest/ltl2tgba.test: Test two more formulae using [->].
    • Alexandre Duret-Lutz's avatar
      Rewrite Exp[=0..] as [*]. · 2c31e541
      Alexandre Duret-Lutz authored
      * src/ltlast/bunop.cc: Implement this rewriting.
      * src/ltlast/bunop.hh: Document it.
      * src/ltltest/equals.test: Test it.
    • Alexandre Duret-Lutz's avatar
      Introduce [=min..max] operator. · 8d4a413a
      Alexandre Duret-Lutz authored
      * src/ltlast/bunop.hh: Declare bunop::Equal
      * src/ltlast/bunop.cc: Handle it.
      * src/ltlparse/ltlparse.yy,
      src/ltlparse/ltlscan.ll: Add rules for [=min..max].
      * src/tgbaalgos/ltl2tgba_fm.cc: Handle bunop::Equal in
      the translation.
      * src/ltltest/equals.test: Test trivial identities
      for [=min..max].
      * src/tgbatest/ltl2tgba.test: Add new formulae to test.
    • Alexandre Duret-Lutz's avatar
      Add functions to compute the kind of a formula (LTL, PSL, Boolean...) · 437128b5
      Alexandre Duret-Lutz authored
      * src/ltlvisit/kind.hh, src/ltlvisit/kind.cc: New files.
      * src/ltlvisit/Makefile.am: Add them.
      * src/ltltest/kind.test, src/ltltest/kind.cc: New files.
      * src/ltltest/Makefile.am: Add them.
    • Alexandre Duret-Lutz's avatar
      Add support for [+]. · 567b4607
      Alexandre Duret-Lutz authored
      * src/ltlast/bunop.cc (bunop::format): Output [*1..] as [+].
      * src/ltlvisit/tostring.cc: Output "a*" as "a[*]" for consistency.
      * src/ltlparse/ltlparse.yy, src/ltlparse/ltlscan.ll: Recognize [+].
      * src/ltltest/tostring.test, src/ltltest/equals.test,
      src/tgbatest/ltl2tgba.test: More tests.
    • Alexandre Duret-Lutz's avatar
      Add support the bounded star operator [*i..j]. · 126b724a
      Alexandre Duret-Lutz authored
      * src/ltlast/bunop.hh, src/ltlast/bunop.cc: New files for
      bounded unary operators.
      * src/ltlast/Makefile.am, src/ltlast/allnodes.hh: Add them.
      * src/ltlast/predecl.hh (bunop): Declare.
      * src/ltlast/unop.hh, src/ltlast/unop.cc (Star): Remove
      declaration of Star and associated code.
      * src/ltlast/visitor.hh: Add visit(bunop* node) methods.
      * src/ltlparse/ltlparse.yy, src/ltlparse/ltlscan.ll: Add parse
      rules for LTL.  This required passing the parse_error list
      to the lexer, so it can report scanning errors when it reads
      a number that does not fit in an unsigned int.
      * src/ltlparse/parsedecl.hh (YY_DECL): Take error_list
      as third argument.
      * src/ltltest/consterm.test, src/ltltest/tostring.test,
      src/ltltest/equals.test, src/tgbatest/ltl2tgba.test: More tests.
      * src/ltlvisit/basicreduce.cc, src/ltlvisit/clone.cc,
      src/ltlvisit/clone.hh, src/ltlvisit/consterm.cc,
      src/ltlvisit/dotty.cc, src/ltlvisit/mark.cc,
      src/ltlvisit/nenoform.cc, src/ltlvisit/postfix.cc,
      src/ltlvisit/postfix.hh, src/ltlvisit/reduce.cc,
      src/ltlvisit/syntimpl.cc, src/ltlvisit/tostring.cc,
      src/ltlvisit/tunabbrev.cc, src/tgba/formula2bdd.cc,
      src/tgbaalgos/eltl2tgba_lacim.cc, src/tgbaalgos/ltl2taa.cc,
      src/tgbaalgos/ltl2tgba_lacim.cc: Adjust syntax to use
      "bunop::Star" instead of "unop::Star".
      * src/tgbaalgos/ltl2tgba_fm.cc: Likewise, but also adjust
      the code to handle the bounds of the operator.
    • Alexandre Duret-Lutz's avatar
      Print '{!a}*' rather than '!a*'. · 47b2bea8
      Alexandre Duret-Lutz authored
      * src/ltlvisit/tostring.cc: Use braces for unary operators in
      * src/ltltest/tostring.test: Add some PSL formulae, it cannot
    • Alexandre Duret-Lutz's avatar
      Accept "{E}|->ltl" and "{E}(ltl)" as synonym for "{E}[]->ltl". · 1ecc6984
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlparse.yy (parenthesedsubformula): Extract these
      rules from...
      (subformula): ... here, and use it to recognize "{SERE}(formula)".
      * src/ltlparse/ltlscan.ll: Recognize "|->" as "[]->".
      * src/ltltest/equals.test: Test these two new syntaxes.
    • Alexandre Duret-Lutz's avatar
      Use [*0] instead of #e, and support [*] in addition to *. · 8b8633de
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlscan.ll: Recognize [*] as *, and use
      [*0] instead of #e for the empty word.
      * src/ltlast/binop.cc, src/ltlast/constant.cc,
      src/ltlast/multop.cc, src/ltlast/multop.hh, src/ltlast/unop.cc,
      src/ltlast/unop.hh, src/ltltest/consterm.test,
      src/ltltest/equals.test: Adjust all occurrences of #e to [*0].
      * src/tgbatest/ltl2tgba.test: Also use [*].
    • Alexandre Duret-Lutz's avatar
      Support braces in addition to parentheses in rational expressions. · 4e7233d9
      Alexandre Duret-Lutz authored
      * src/ltlparse/ltlparse.yy (rationalexp): Allow bracedrationalexp.
      * src/ltltest/consterm.test, src/tgbatest/ltl2tgba.test: Add more