Skip to content

GitLab

Switch branch/tag
  1. 05 Dec, 2014 1 commit
  3. 17 May, 2014 1 commit
    • Alexandre Duret-Lutz's avatar
      snf: Fix the handling of bounded repetition. · 139f7b49
      Alexandre Duret-Lutz authored 
      star_normal_form() used to be called under bounded
repetitions like [*0..4], but some of these rewritings
are only correct for [*0..].  For instance
     (a*|1)[*]      can be rewritten to    1[*]
but  (a*|1)[*0..1]  cannot be rewritten to 1[*0..1]
it would be correct to rewrite the latter as (a[+]|1)[*0..1],
canceling the empty word in a*.

Also (a*;b*)[*]     can be rewritten to    (a|b)[*]
but  (a*;b*)[*0..1]  cannot be rewritten to (a|b)[*0..1]
and it cannot either be rewritten to (a[+]|b[+])[*0..1].

This patch introduces a new function to implement
rewritings under bounded repetition.

* src/ltlvisit/snf.hh, src/ltlvisit/snf.cc (star_normal_form_unbounded):
New function.
* src/ltlvisit/simplify.cc: Use it.
* src/ltltest/reduccmp.test: Add tests.
* doc/tl/tl.tex: Document the rewritings implemented.
      139f7b49
  5. 16 May, 2014 1 commit
    • Alexandre Duret-Lutz's avatar
      snf: Fix the handling of bounded repetition. · 05ed3def
      Alexandre Duret-Lutz authored 
      star_normal_form() used to be called under bounded
repetitions like [*0..4], but some of these rewritings
are only correct for [*0..].  For instance
     (a*|1)[*]      can be rewritten to    1[*]
but  (a*|1)[*0..1]  cannot be rewritten to 1[*0..1]
it would be correct to rewrite the latter as (a[+]|1)[*0..1],
canceling the empty word in a*.

Also (a*;b*)[*]     can be rewritten to    (a|b)[*]
but  (a*;b*)[*0..1]  cannot be rewritten to (a|b)[*0..1]
and it cannot either be rewritten to (a[+]|b[+])[*0..1].

This patch introduces a new function to implement
rewritings under bounded repetition.

* src/ltlvisit/snf.hh, src/ltlvisit/snf.cc (star_normal_form_unbounded):
New function.
* src/ltlvisit/simplify.cc: Use it.
* src/ltltest/reduccmp.test: Add tests.
* doc/tl/tl.tex: Document the rewritings implemented.
      05ed3def
  7. 13 May, 2014 2 commits
    • Alexandre Duret-Lutz's avatar
      simplify: remove an incorrect simplification rule · d741d926
      Alexandre Duret-Lutz authored 
      Fortunately was only enabled with the
ltl_simplifier_options::favor_event_univ option, which cannot yet be
turned on from the command-line tools.

* src/ltlvisit/simplify.cc, doc/tl/tl.tex: Remove the rule.
* src/ltltest/eventuniv.test: Adjust.
* NEWS: Mention the bug.
      d741d926
    • Alexandre Duret-Lutz's avatar
      simplify: fix 3 incorrect simplification rules · 48471b51
      Alexandre Duret-Lutz authored 
      * src/ltlvisit/simplify.cc: Remove two incorrect rules, and
partially disable another one.
* doc/tl/tl.tex: Reflect the change.
* src/ltltest/reduccmp.test: Likewise.
* src/ltltest/equals.cc: Add safety checks to catch such errors in the
future.
* NEWS: Mention the bug.
      48471b51
  9. 17 Oct, 2013 1 commit
  11. 29 Jul, 2013 1 commit
    • Alexandre Duret-Lutz's avatar
      Fix interpretation of {e[*]} and !{e[*]}. · cb7bdf8c
      Alexandre Duret-Lutz authored 
      This follows from a discussion with Ernesto Posse.

The semantics for the {...} operator we use in Spot comes from the
cl(...) operator defined by Dax et al. (ATVA'09).  This is slightly
different from the the way the PSL spec interprets a SERE used in the
context of a temporal formula (appendix B.3.1.1.2, item 7).

cl({a;b}[*]) would match any infinite word that starts with a;b, while
in PSL {a;b}[*] would match any infinite word that alternates a and b.

Spot documents that {SERE} in a temporal formula is interpreted like
cl(SERE) however it failed to ignore the empty prefix of SERE.  So
{{a;b}[*]} would match anything, because the empty word is a prefix of
any word, and is also accepted by {a;b}[*].  Some trivial identities
and basic rewritings were also wrongly considering these empty
prefixes as well.

This patch therefore fixes the translation and syntactic
simplification rules, to really ignore these empty prefixes.

In some future version it should probably be wise to rename this {...}
operator as cl(...), and use {...} for the semantics given in appendix
B.3.1.1.2 (item 7) of the PSL specs.

* src/ltlast/unop.cc: Fix trivial identities.  We have
{[*0]} = 0 and !{[*0]} = 1.
* src/ltlvisit/simplify.cc: Fix basic rewriting rules.
{e[*]} = {e} and !{e[*]} = !{e}.
* doc/tl/tl.tex: Adjust documentation.
* doc/tl/tl.bib (dax.09.atva): New entry.
* src/tgbaalgos/ltl2tgba_fm.cc: Do not accept any
infinite word for {e[*]} just because the empty
prefix is matched by e[*].
* src/tgbatest/ltl2tgba.test: Add a test case.
* NEWS: Mention it.
* THANKS: Add Ernesto.
      cb7bdf8c
  13. 27 Apr, 2013 1 commit
    • Alexandre Duret-Lutz's avatar
      Implement a favor_even_univ option in the rewriting rules. · 9caa9ad1
      Alexandre Duret-Lutz authored 
      The set of rules enabled by favor_even_univ try to "lift" the
subformulae that are both eventual and universal, so they appear
higher in the AST.  This is contrary to what we used to do (and still
do when the option is unset), were we try to postpone such subformulae
(by moving them down the AST).  It is still a bit experimental.

* src/ltlvisit/simplify.hh: Add option favor_event_univ.
* src/ltlvisit/simplify.cc: Implement new rewriting rules.
* doc/tl/tl.tex: Document them.
* src/tgbatest/ltl2tgba.cc: Add option -ra to enable them.
* src/tgbatest/spotlbtt.test: Test the translation with this option.
* src/ltltest/reduc.cc, src/ltltest/equals.cc: Add option
to enable the new rules.
* src/ltltest/eventuniv.test: New file to test them.
* src/ltltest/Makefile.am: Add it.
      9caa9ad1
  15. 11 Jan, 2013 1 commit
  17. 14 Oct, 2012 1 commit
    • Alexandre Duret-Lutz's avatar
      Add a has_lbt_atomic_props() method to LTL formulas. · b2de0136
      Alexandre Duret-Lutz authored 
      * src/ltlast/formula.hh (has_lbt_atomic_props): New method.
* src/ltlast/formula.cc (printprops): Display it.
* src/ltlast/atomic_prop.cc: Update it.
* src/bin/ltlcheck.cc, src/bin/genltl.cc: Use it.
* doc/tl/tl.tex: Menton has_lbt_atomic_props().
      b2de0136
  19. 24 Sep, 2012 2 commits
  21. 29 Aug, 2012 1 commit
    • Alexandre Duret-Lutz's avatar
      Add back the '*' syntax for And. · 5939d6f4
      Alexandre Duret-Lutz authored 
      This somehow revert changes from 2010-01-30 which killed this use of
star to make room for the Kleen star.  Here we only allow '*' in the
temporal formula, so that it can still be the Kleen star in SERE.  The
motivation for '*' available as And is better compatibility with Wring
and VIS.

* src/ltlparse/ltlscan.ll: Distinguish * from [*].
* src/ltlparse/ltlparse.yy: Allows * to be used as AND between
temporal formulae.
* src/ltltest/equals.test, src/ltltest/parse.test: Add a few
tests.
* doc/tl/tl.tex: Document it.
      5939d6f4
  23. 05 Jun, 2012 1 commit
  25. 04 Jun, 2012 2 commits
  27. 12 May, 2012 1 commit
    • Alexandre Duret-Lutz's avatar
      Fix translation of !{r}. · e2f70e72
      Alexandre Duret-Lutz authored 
      We need a marked version of !{r} to perform breakpoint unroling.

* src/ltlast/unop.cc, src/ltlast/unop.hh: Declare a NegClosureMarked
operator.
* src/ltlvisit/mark.hh, src/ltlvisit/mark.cc,
src/tgbaalgos/ltl2tgba_fm.cc: Adjust to deal with NegClosureMarked
and NegClosure as apropriate.
* src/ltlvisit/simplify.cc, src/ltlvisit/tostring.cc,
src/ltlvisit/tunabbrev.cc, src/tgbaalgos/eltl2tgba_lacim.cc,
src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2tgba_lacim.cc,
src/tgba/formula2bdd.cc: Deal with NegClosureMarked in the same way as
we deal with NegClosure.
* src/tgbatest/ltl2tgba.test: More tests.
* src/ltltest/kind.test: Adjust.
* doc/tl/tl.tex: Mention the marked negated closure.
      e2f70e72
  29. 07 May, 2012 1 commit
  31. 02 May, 2012 1 commit
  33. 30 Apr, 2012 8 commits
  35. 28 Apr, 2012 13 commits