Spot 0.7.1 used to need 190 acceptance conditions to translate the
188 literature formulae.  With this patch we are down to 185.
That's not an impressive, but there are only ~20 formulae that
require more than 1 acceptance conditions; hence little room for
improvement.

* src/misc/bddlt.hh (bdd_hash): New function.
* src/misc/accconv.hh, src/misc/accconv.cc: New files.
* src/misc/Makefile.am: Add them.
* src/tgbaalgos/scc.cc (scc_map::build_map): Adjust
to record all combination of acceptance conditions occurring in a SCC.
* src/tgbaalgos/scc.hh (scc_map::scc::useful_acc): Update description.
* src/tgbaalgos/sccfilter.cc (scc_filter): Simplify acceptance
conditions that are always implied by another acceptance
conditions.  Previously, we only removed acceptance conditions
that where always present in accepting SCCs.
* src/tgbatest/sccsimpl.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add it.

* src/tgbaalgos/save.c (process_state): Escape quotes in the
name of source and destination states.  This fixes a side bug
in the upcoming degenid.test test case.

after the simulation-reduction.

Report from Tomáš Babiak <xbabiak@fi.muni.cz>.

* src/tgbaalgos/neverclaim.hh (never_claim_reachable): Take
a tgba as input.
* src/tgbaalgos/neverclaim.cc (never_claim_bfs): Call
state_is_accepting() only if this tgba turns out to be
a tgba_sba_proxy.  Otherwise check the acceptance of one
outgoing transition as we do in dotty_bfs since 2011-03-05.
* src/tgbatest/ltl2tgba.cc: Do not redegeneralize before
calling never_claim_reachable() if we know the automaton is
degeneralized already.
* src/tgbatest/ltl2tgba.test: Add a test case.

* src/misc/casts.hh: New file.
* src/misc/Makefile.am: Add it.
* iface/dve2/dve2.cc, iface/gspn/gspn.cc, iface/gspn/ssp.cc,
src/evtgba/explicit.cc, src/evtgba/product.cc, src/misc/casts.hh,
src/tgba/state.hh, src/tgba/statebdd.cc, src/tgba/taatgba.cc,
src/tgba/taatgba.hh, src/tgba/tgbabddconcrete.cc,
src/tgba/tgbaexplicit.cc, src/tgba/tgbaexplicit.hh,
src/tgba/tgbakvcomplement.cc, src/tgba/tgbaproduct.cc,
src/tgba/tgbasafracomplement.cc, src/tgba/tgbasgba.cc,
src/tgba/tgbatba.cc, src/tgba/tgbaunion.cc, src/tgba/wdbacomp.cc,
src/tgbaalgos/ndfs_result.hxx, src/tgbaalgos/reductgba_sim.cc,
src/tgbaalgos/reductgba_sim_del.cc: Use down_cast when
appropriate.

* src/sanity/style.test: Catch some binary operators not
delimited with spaces.
* src/tgbaalgos/bfssteps.cc, src/tgbaalgos/magic.cc,
src/tgbaalgos/reducerun.cc, src/tgbaalgos/se05.cc,
src/tgbaalgos/tau03.cc, src/tgbaalgos/tau03opt.cc: Fix these.

* src/tgbaalgos/dotty.hh (dotty_reachable): Take a new
assume_sba argument.
* src/tgbaalgos/dotty.cc (dotty_bfs): Take a new
mark_accepting_states arguments.
(dotty_bfs::process_state): Check if a state is accepting using
the state_is_accepting() method for tgba_sba_proxies, or by
looking at the first outgoing transition of the state.  Pass
the result to the dectorator.
(dotty_reachable): Adjust function.
* src/tgbaalgos/dottydec.hh, src/tgbaalgos/dottydec.cc,
src/tgbaalgos/rundotdec.hh, src/tgbaalgos/rundotdec.cc
(state_decl): Add an "accepting" argument, and use it to
decorate accepting states with a double border.
* src/tgbatest/ltl2tgba.cc: Keep track of whether the output
is an SBA or not, so that we can tell it to dotty().
* wrap/python/ajax/spot.in: Likewise.
* wrap/python/cgi-bin/ltl2tgba.in: Likewise.

* src/tgbaalgos/minimize.cc (build_result): Speed it up by
removing one useless loop, creating many duplicate transitions
that had to be merged.

* src/tgbaalgos/minimize.cc (build_result, minimize_dfa,
minimize_wdba): Correctly handle (i.e. ignore) useless states.
* src/tgbatest/ltl2tgba.test: Add two more tests.

* src/tgbaalgos/stats.hh (tgba_sub_statistics): New class.
(sub_stats_reachable): New function.
* src/tgbaalgos/stats.cc (sub_stats_bfs): New class.
(tgba_sub_statistics::dump, sub_stats_reachable): New function.
* src/tgbatest/ltl2tgba.cc (-kt): New option.
* src/tgbatest/ltl2tgba.test: Use -kt.

* src/tgbaalgos/minimize.cc (minimize_monitor): Fix typo yielding
incorrect monitor if the input tgba is not deterministic.
* src/tgbatest/ltl2tgba.test: Add test case.

implement is_safety_mwdba().

Note: I swapped the name of safety and guarantee when I
implemented is_safety_automaton() on 2010-03-20.  Fortunately,
is_safety_automaton() was only used where is_guarantee_automaton()
would have been correct.

* src/tgbaalgos/safety.cc (is_guarantee_automaton): Rename as ...
(is_guarantee_automaton): ... this.
(is_safety_mwdba): New function.
* src/tgbaalgos/safety.hh: Adjust and add documentation.
* src/tgbaalgos/minimize.cc: Use is_guarantee_automaton() instead
of is_safety_automaton().
* src/tgbatests/safety.test: Rename as ...
* src/tgbatests/obligation.test: ... this, and augment the
test.
* src/tgbatest/Makefile.am: Adjust.
* src/tgbatest/ltl2tgba.cc (-O): Display whether a formula
represent a safety, guarantee, or obligation property.
* NEWS: Adjust.

* src/tgba/succiter.hh, src/tgba/tgba.hh,
src/tgba/tgbabddconcrete.hh, src/tgba/tgbaproduct.hh,
src/tgba/tgbaunion.hh, src/tgbaalgos/bfssteps.hh,
src/tgbaalgos/gtec/ce.cc, src/tgbaalgos/gtec/explscc.hh,
src/tgbaalgos/gtec/gtec.cc, src/tgbaalgos/replayrun.cc,
src/tgbaalgos/scc.cc, src/tgbaalgos/scc.hh: Update comments
to say that we "destroy" a state instead of "deleting" it.

Right now, destroy() just executes "delete this".  But in a later
version, we will rewrite tgba_explicit so that it does not
allocate new states (and the destroy() method for explicit state
will do nothing).

* src/tgba/state.hh (state::destroy): New method, to replace
state::~state() in the future.
(shared_state_deleter): New function.
* src/evtgba/product.cc, src/evtgbaalgos/reachiter.cc,
src/evtgbaalgos/save.cc, src/evtgbaalgos/tgba2evtgba.cc,
src/tgba/tgba.cc, src/tgba/tgbaproduct.cc, src/tgba/tgbareduc.cc,
src/tgba/tgbasafracomplement.cc, src/tgba/tgbasgba.cc,
src/tgba/tgbatba.cc, src/tgba/tgbaunion.cc, src/tgba/wdbacomp.cc,
src/tgbaalgos/cutscc.cc, src/tgbaalgos/emptiness.cc,
src/tgbaalgos/gtec/ce.cc, src/tgbaalgos/gtec/explscc.cc,
src/tgbaalgos/gtec/gtec.cc, src/tgbaalgos/gtec/nsheap.cc,
src/tgbaalgos/gv04.cc, src/tgbaalgos/magic.cc,
src/tgbaalgos/minimize.cc, src/tgbaalgos/ndfs_result.hxx,
src/tgbaalgos/neverclaim.cc, src/tgbaalgos/powerset.hh,
src/tgbaalgos/reachiter.cc, src/tgbaalgos/reducerun.cc,
src/tgbaalgos/reductgba_sim.cc,
src/tgbaalgos/reductgba_sim_del.cc, src/tgbaalgos/replayrun.cc,
src/tgbaalgos/safety.cc, src/tgbaalgos/save.cc,
src/tgbaalgos/scc.cc, src/tgbaalgos/se05.cc,
src/tgbaalgos/tau03.cc, src/tgbaalgos/tau03opt.cc: Adjust to call
"s->destroy()" instead of "delete s".
* src/saba/sabacomplementtgba.cc, src/tgba/tgbakvcomplement.cc:
Pass shared_state_deleter to the shared_ptr constructor, so that
it calls destroy() instead of delete.

* src/tgbaalgos/minimize.cc (minimize_dfa): Fix deletion of the
state_set_map.  It led to a crash when compiled with g++-3.3.

translation contain useless SCCs that where not ignored for
minimization.

* src/tgbaalgos/minimize.cc (minimize_wdba): Strip useless
SCCs before minimization.
* src/tgbatest/ltl2tgba.test: Add a check.

* src/tgbaalgos/minimize.cc (minimize_dfa): Take final and
non_final sets.
(minimize_wdba): Fill in non_final at the same time as final.
(minimize_monitor): Call state_set() to fill non_final.
(init_sets): Simplify and rename as ...
(state_set): ... this.

* src/tgba/wdbacomp.hh, src/tgba/wdbacomp.cc: New file.
* src/tgba/Makefile.am: Add them.
* src/tgbaalgos/minimize.cc (minimize_obligation): Use
wdba_complement().

* src/tgbaalgos/minimize.hh, src/tgbaalgos/minimize.cc
(minimize): Split into ...
(minimize_wdba, minimize_monitor): ... these two functions.
* src/tgbatest/ltl2tgba.cc (main): Adjust the call to
minimize_monitor.
* wrap/python/cgi-bin/ltl2tgba.in: Adjust the calls to
minimize_monitor and minimize_obligation.
* wrap/python/spot.i: Declare minimize_monitor, minimize_wdba,
minimize_obligations.
* src/tgba/tgbaexplicit.hh (tgba_explicit_string)
(tgba_explicit_formula, tgba_explicit_number): Add fake
declarations so that SWIG can see they inherits from tgba.

* src/tgbaalgos/minimize.cc (minimize):  Move the minimization
code into...
(minimize_dfa): ... this new function, and fix the condition
under which a partition is considered to be minimal.  Also
use a map instead of a list to lookup known formulae.

* src/tgbaalgos/minimize.cc (minimize_obligation): Do not
minimize aut_neg_f, complement min_aut_f instead.
* src/tgbaalgos/minimize.hh: Adjust description.

to label transient states.

* src/tgbaalgos/powerset.hh (power_map): New structure, allowing
the caller to retrieve the set of original states corresponding to
the set in the deterministic automaton.
(power_set): Adjust prototype to take a power_map instead of the
acc_list.
* src/tgbaalgos/powerset.cc (power_set): Strip all code using
acc_list, and update power_set.
* src/tgbaalgos/minimize.cc (minimize): Rewrite, using an
algorithm similar to the one in the Dax paper to check whether
state of the minimized automaton should be accepting.

* src/tgbaalgos/scc.hh, src/tgbaalgos/scc.cc (scc_map::trivial,
scc_map::one_state_of): Two new helper functions.

correct from ltl2tgba to the library.

* src/tgbaalgos/minimize.hh,
src/tgbaalgos/minimize.cc (minimize_obligation): New function.
* src/tgbatests/ltl2tgba.cc (main): Fix constness of automata,
and call minimize_obligation() for -R3b.

* src/tgbatest/ltl2tgba.cc (-M): New option for building
deterministic monitors.
* src/tgbaalgos/minimize.cc (minimize): Take a monitor
argument and adjust the code.
* src/tgbaalgos/minimize.hh (minimize): Document it.

* src/tgbaalgos/minimize.cc (init_sets, minimize): Fix memory
leaks and a usage of the wrong automaton.
* src/tgbatest/wdba.test: Try using -Rm with -R3 or -R3b, and with
valgrind.  This caught all the bugs fixed above.

* src/tgbaalgos/minimize.cc (minimize): Don't add acceptance
conditions if the final set is empty.
* src/tgbaalgos/powerset.cc (tgba_powerset): Add the initial state
to acc_list if it is accepting.  Also do not compute an SCC build
map if we don't have to build acc_list.

* src/tgbatest/ltl2tgba.cc (main): Delete the minimized automaton.
* src/tgbaalgos/minimize.cc (minimize): Remove the call to
unregister_variable() at the end.  It was both
wrong (unregistering only the first variable) and useless ("delete
del_a" will unregister all these variables).  Use a map and a set
to keep track of free BDD variable and reuse them, otherwise the
algorithm would sometimes use more variables than allocated.

* src/tgbaalgos/safety.hh, src/tgbaalgos/safety.cc: New
files.
* src/tgbaalgos/Makefile.am: Add them.
* src/tgbatests/ltl2tgba.cc: Add option "-O".
* src/tgbaalgos/scc.hh: Update documentation.
* src/tgbatest/Makefile.am (TESTS): Add safety.test.
* src/tgbatest/safety.test: New file.

Felix Abecassis authored Mar 20, 2010 and Alexandre Duret-Lutz committed Jan 05, 2011

* src/tgbatest/minimize.cc: Delete useless includes.
* src/tgbaalgos/minimize.cc: Delete useless includes,
fixed acceptance conditions.
* src/tgbatest/ltl2tgba.cc: Add -Rm option for minimization.
* src/tgba/tgbaexplicit.cc: Fixed typo.

Felix Abecassis authored Mar 20, 2010 and Alexandre Duret-Lutz committed Jan 05, 2011

New files.  Algorithm to minimize an automaton using first the powerset
construction to determinize the input automaton, the automaton is then
minimized using the standard algorithm, using BDDs to check if states
are equivalent.

Felix Abecassis authored Mar 20, 2010 and Alexandre Duret-Lutz committed Jan 05, 2011

from the initial automaton.

* src/tgba/tgbaexplicit.cc, src/tgba/tgbaexplicit.hh:
Added class tgba_explicit_number, a tgba_explicit where states are
labelled by integers.
* src/tgbaalgos/powerset.hh, src/tgbaalgos/powerset.cc:
When building the deterministic automaton, keep track of which states
were created from an accepting state in the initial automaton.
The states are added to the new optional parameter (if not 0),
acc_list.
Use tgba_explicit_number instead of tgba_explicit_string to build
the result.
* src/tgbaalgos/scc.cc (spot): Small fix.
Print everything on std::cout.

* src/tgbaalgos/reducerun.hh (tgba_run): Predeclare as a struct
since this is what it is.
* src/tgbatest/randtgba.cc (main): Avoid using "i" with two
different type in the same loop.

* src/ltlast/binop.cc, src/ltlast/binop.cc: Add support for
these new operators.
* src/ltlparse/ltlparse.yy, src/ltlparse/ltlscan.ll: Parse them.
* src/ltltest/reduccmp.test: Add new tests for W and M.
* src/ltlvisit/basicreduce.cc, src/ltlvisit/contain.cc,
src/ltlvisit/lunabbrev.cc, src/ltlvisit/nenoform.cc,
src/ltlvisit/randomltl.cc, src/ltlvisit/randomltl.hh,
src/ltlvisit/reduce.cc, src/ltlvisite/simpfg.cc,
src/ltlvisit/simpfg.hh, src/ltlvisit/syntimpl.cc,
src/ltlvisit/tostring.cc, src/tgba/formula2bdd.cc,
src/tgbaalgos/eltl2tgba_lacim.cc, src/tgbaalgos/ltl2taa.cc,
src/tgbaalgos/ltl2tgba_fm.cc, src/tgbaalgos/ltl2tgba_lacim.cc:
Add support for W and M.
* src/tgbatest/ltl2neverclaim.test: Test never claim output
using LBTT, this is more thorough.  Also we cannot use -N
any more in the spotlbtt.test.
* src/tgbatests/ltl2tgba.cc: Define M and W for ELTL.
* src/tgbatest/ltl2neverclaim.test: Test W and M, and use
-DS instead of -N, because lbtt-translate does not want
to translate these operators for tools that masquerade as Spin.

by default in scc_filter().

Doing so helps the degeneralization algorithm, because it will
have more opportunity to be in an accepting level when it reaches
the accepting SCCs.

* src/tgbaalgos/sccfilter.cc (filter_iter::filter_iter): Take a
remove_all_useless argument.
(filter_iter::process_link): Use the flag to decide whether to
filter acceptance conditions going to accepting SCCs.
(scc_filter): Take a remove_all_useless argument and pass it to
filter_iter.
* src/tgbaalgos/sccfilter.hh (filter_iter): Add the new argument
and document the function.
* src/tgbatest/tgbatests/ltl2tgba.cc (main): Add option use -R3
for remove_all_useless=false and add -R3f for
remove_all_useless=true.
* src/tgbatest/ltl2tgba.test: Show one case where -R3f makes
the degeneralization worse than -R3.

This is actually the third time I fix random_graph().  On
2007-02-06 I changed the function not to generated dead states,
but in a way that made it non-deterministic.  On 2010-01-20 I made
the function deterministic again, but it started to generate dead
states as a side effect.  This time, I'm making sure that dead
states won't come again with a test-case that we should have had
from the beginning.

* src/tgbaalgos/randomgraph.cc (random_graph): Add an extra
indirection array, state_randomizer[], so that we can reorder
states indices after a random selection without actually changing
the value of the indices used by unreachable_states and
nodes_to_process.
* src/tgbatest/randtgba.test: New file.
* src/tgbatest/Makefile.am: Add randtgba.test.