* src/neverparse/public.hh, src/neverparse/parsedecl.hh: Fix
inclusion guards.
* src/tgba/tgbaexplicit.hh, src/tgbatest/emptchk.test,
src/tgbatest/ltl2tgba.cc: Fix trailing whitespaces.

ltl2ba.

* src/neverparse/neverclaimparse.yy: Accept multiple labels
for the same state.  Honor accepting states.  Forward parse
error from the parser used for guards.  Accept "false" as a
single instruction for a state.
* src/neverparse/neverclaimscan.ll: Recognize "false" specifically,
and remove the ";" hack.
* src/tgba/tgbaexplicit.cc
(tgba_explicit_string::~tgba_explicit_string): Adjust not to
destroy a state twice.
* src/tgba/tgbaexplicit.hh
(tgba_explicit_string::add_state_alias): New function.
* src/tgbatest/defs.in (SPIN, LTL2BA): New variables.
* src/tgbatest/neverclaimread.test: Check error messages for
syntax errors in guards.  Make sure we can read the output
of `spin -f' and `ltl2ba -f' on a few test formulae.

We do that because the declaration of this type, which is local to
src/tgba/tgbasafracomplement.cc has a member in an anonymous
namespace, and some versions of g++-4.2 issue a very annoying
warning about this legitimate code.  See Bug 29365 on GCC's
Bugzilla.  Report by Silien Hong <silien.hong@lip6.fr>.

* src/tgba/tgbasafracomplement.hh (safra_tree_automaton): Do not
forward declare.
(tgba_safra_complement): Use void* instead of
safra_tree_automaton*.
* src/tgba/tgbasafracomplement.cc: static_cast void* to
safra_tree_automaton* anywhere needed.

* 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.

degeneralization.

* src/tgba/tgbatba.cc (tgba_sba_proxy::tgba_tba_proxy): Build the
list of acceptance condition in the reverse order.  The order is
still arbitrary, but the bdd_satone() call seems to output the
acceptance conditions that are more used first, and this helps the
degeneralization process.

* src/tgba/tgbatba.cc (tgba_sba_proxy::tgba_sba_proxy): Do not
forget to free the initial state after usage.

* src/tgba/tgbatba.cc (tgba_sba_proxy::tgba_sba_proxy): Set
cycle_start_ to start in the accepting layer of the degeneralized
automaton if the initial state has an accepting self-loop.
Otherwise, starts at the level of the first acceptance condition
as previously.
(tgba_sba_proxy::get_init_state): Use cycle_start_.
* src/tgba/tgbatba.hh (tgba_tba_proxy::a_): Make it protected so
that we can use it in tgba_sba_proxy::tgba_sba_proxy.
(tgba_sba_proxy::cycle_start_, tgba_sba_proxy::get_init_state):
Declare.
* src/tgbatest/ltl2tgba.test: More tests.

* src/tgba/tgbatba.cc (tgba_tba_proxy_succ_iterator::sync_): Move
the optimization step added by the previous patch outside the
before the bddtrue check, so that it also applies to accepting
states in SBA.

an acceptance condition on all outgoing transitions.

This was motivated by experiments from Rüdiger Ehlers, showing
that "ltl2ba -f 'a U (b U c)'" outperformed "ltl2tgba -f -N -R3 'a
U (b U c)'".  With this change and the previous one, it is no
longer the case.

* src/tgba/tgbatba.cc (tgba_tba_proxy_succ_iterator::aut_): Store
a pointer to the source automaton and...
(tgba_tba_proxy_succ_iterator::sync_): ... use it in an extra
optimization step to gather the acceptance conditions common
to all outgoing transitions of the destination state, and pretend
they are on the current (ingoing) transition.
(tgba_tba_proxy::succ_iter): Pass the
source automaton to the constructed iterator.
* src/tgbatest/spotlbtt.test: Test -f -N -R3 -r7.
* src/tgbatest/ltl2tgba.test: Add a test case for 'a U (b U c)'.

* src/tgba/tgbakvcomplement.hh: Use \verbatim around the bibtex
entry.
* src/saba/sabacomplementtgba.hh: Use latin1.

* src/tgba/tgbafromfile.cc, src/tgba/tgbafromfile.hh: Delete these
files.
* src/tgba/Makefile.am: Remove them.
* src/ltl/ltlparse/ltlfile.hh, src/ltl/ltlparse/ltlfile.cc: New
files.
* src/ltl/ltlparse/Makefile.am: Add them.
* bench/scc-stats/stats.cc, bench/split-product/cutscc.cc: Rewrite
using the new class.

* eltlparse/public.hh, saba/saba.hh, tgba/tgbakvcomplement.hh,
tgba/tgbasafracomplement.hh, tgbaalgos/eltl2tgba_lacim.cc,
tgbaalgos/eltl2tgba_lacim.hh, tgbaalgos/ltl2taa.hh: Comment
changes.

* src/tgbaalgos/ltl2tgba_fm.cc, src/tgbaalgos/ltl2tgba_fm.hh:
Remove the containment option.
* src/tgbafromfile.cc, src/tgbafromfile.hh: Remove the
containment_ member.
* src/tgbatest/ltl2tgba.cc (syntax): Remove -c option for
FM algorithm, use it exclusively for TAA.

fix some comments.

* src/tgba/tgbacomplement.hh, src/tgba/tgbacomplement.cc: Rename
as...
* src/tgba/tgbakvcomplement.hh, src/tgba/tgbakvcomplement.cc:
... these. It makes more sense since we also have
tgba_safra_complement.
* src/tgba/Makefile.am, src/tgbatest/complement.cc, NEWS: Adjust.

Darwin.

* bench/Makefile.am, bench/gspn-ssp/Makefile.am,
bench/gspn-ssp/defs.in, bench/scc-stats/Makefile.am,
bench/split-product/Makefile.am, configure.ac,
iface/Makefile.am, iface/gspn/Makefile.am, iface/gspn/ssp.hh,
iface/nips/Makefile.am, iface/nips/common.cc,
iface/nips/common.hh, iface/nips/dottynips.cc,
iface/nips/nips.cc, iface/nips/nips.hh, src/Makefile.am,
src/eltlparse/Makefile.am, src/eltlparse/eltlparse.yy,
src/eltlparse/eltlscan.ll, src/eltlparse/fmterror.cc,
src/eltlparse/parsedecl.hh, src/eltltest/Makefile.am,
src/eltltest/defs.in, src/eltltest/nfa.cc, src/evtgba/evtgba.hh,
src/evtgba/product.cc, src/evtgba/product.hh,
src/evtgbaalgos/tgba2evtgba.cc, src/evtgbaparse/Makefile.am,
src/evtgbaparse/evtgbaparse.yy, src/evtgbatest/defs.in,
src/evtgbatest/explicit.test, src/evtgbatest/ltl2evtgba.cc,
src/evtgbatest/ltl2evtgba.test, src/evtgbatest/product.cc,
src/evtgbatest/product.test, src/evtgbatest/readsave.cc,
src/evtgbatest/readsave.test, src/ltlast/atomic_prop.cc,
src/ltlast/atomic_prop.hh, src/ltlast/binop.cc,
src/ltlast/binop.hh, src/ltlast/constant.cc,
src/ltlast/constant.hh, src/ltlast/formula.cc,
src/ltlast/formula.hh, src/ltlast/formula_tree.cc,
src/ltlast/formula_tree.hh, src/ltlast/multop.cc,
src/ltlast/multop.hh, src/ltlast/nfa.cc, src/ltlast/nfa.hh,
src/ltlast/unop.cc, src/ltlast/unop.hh, src/ltlenv/declenv.cc,
src/ltlenv/declenv.hh, src/ltlenv/environment.hh,
src/ltlparse/Makefile.am, src/ltlparse/ltlparse.yy,
src/ltltest/Makefile.am, src/ltltest/defs.in,
src/ltltest/equals.cc, src/ltltest/equals.test,
src/ltltest/lunabbrev.test, src/ltltest/nenoform.test,
src/ltltest/parse.test, src/ltltest/parseerr.test,
src/ltltest/randltl.cc, src/ltltest/readltl.cc,
src/ltltest/reduccmp.test, src/ltltest/syntimpl.cc,
src/ltltest/syntimpl.test, src/ltltest/tostring.cc,
src/ltltest/tostring.test, src/ltltest/tunabbrev.test,
src/ltltest/tunenoform.test, src/ltlvisit/basicreduce.cc,
src/ltlvisit/clone.cc, src/ltlvisit/clone.hh,
src/ltlvisit/contain.cc, src/ltlvisit/destroy.cc,
src/ltlvisit/destroy.hh, src/ltlvisit/lunabbrev.cc,
src/ltlvisit/nenoform.cc, src/ltlvisit/randomltl.cc,
src/ltlvisit/reduce.cc, src/ltlvisit/syntimpl.cc,
src/ltlvisit/tostring.cc, src/misc/bddalloc.cc,
src/misc/bddop.cc, src/misc/bddop.hh, src/misc/freelist.hh,
src/misc/hash.hh, src/misc/minato.cc, src/misc/minato.hh,
src/misc/optionmap.cc, src/misc/timer.cc, src/misc/timer.hh,
src/saba/Makefile.am, src/saba/explicitstateconjunction.cc,
src/saba/explicitstateconjunction.hh, src/saba/saba.cc,
src/saba/saba.hh, src/saba/sabacomplementtgba.cc,
src/saba/sabacomplementtgba.hh, src/saba/sabastate.hh,
src/saba/sabasucciter.hh, src/sabaalgos/Makefile.am,
src/sabaalgos/sabadotty.cc, src/sabaalgos/sabadotty.hh,
src/sabaalgos/sabareachiter.cc, src/sabaalgos/sabareachiter.hh,
src/sabatest/Makefile.am, src/sabatest/defs.in,
src/sanity/Makefile.am, src/tgba/Makefile.am,
src/tgba/bdddict.cc, src/tgba/bddprint.cc,
src/tgba/formula2bdd.cc, src/tgba/state.hh,
src/tgba/succiterconcrete.cc, src/tgba/taatgba.hh,
src/tgba/tgba.hh, src/tgba/tgbabddconcretefactory.cc,
src/tgba/tgbabddconcretefactory.hh, src/tgba/tgbacomplement.cc,
src/tgba/tgbacomplement.hh, src/tgba/tgbaexplicit.cc,
src/tgba/tgbaexplicit.hh, src/tgba/tgbaproduct.cc,
src/tgba/tgbareduc.cc, src/tgba/tgbareduc.hh,
src/tgba/tgbasafracomplement.cc, src/tgba/tgbasgba.cc,
src/tgba/tgbasgba.hh, src/tgba/tgbaunion.cc,
src/tgba/tgbaunion.hh, src/tgbaalgos/dupexp.cc,
src/tgbaalgos/eltl2tgba_lacim.cc,
src/tgbaalgos/eltl2tgba_lacim.hh, src/tgbaalgos/emptiness.cc,
src/tgbaalgos/gtec/gtec.cc, src/tgbaalgos/ltl2taa.cc,
src/tgbaalgos/ltl2taa.hh, src/tgbaalgos/ltl2tgba_lacim.cc,
src/tgbaalgos/neverclaim.cc, src/tgbaalgos/neverclaim.hh,
src/tgbaalgos/powerset.cc, src/tgbaalgos/reachiter.cc,
src/tgbaalgos/reachiter.hh, src/tgbaalgos/reductgba_sim.cc,
src/tgbaalgos/reductgba_sim.hh,
src/tgbaalgos/reductgba_sim_del.cc, src/tgbaalgos/stats.cc,
src/tgbaalgos/stats.hh, src/tgbaparse/Makefile.am,
src/tgbaparse/tgbaparse.yy, src/tgbatest/Makefile.am,
src/tgbatest/bddprod.test, src/tgbatest/complementation.cc,
src/tgbatest/complementation.test, src/tgbatest/defs.in,
src/tgbatest/dfs.test, src/tgbatest/dupexp.test,
src/tgbatest/explicit.cc, src/tgbatest/explicit.test,
src/tgbatest/explpro3.test, src/tgbatest/explpro4.test,
src/tgbatest/explprod.cc, src/tgbatest/explprod.test,
src/tgbatest/ltl2neverclaim.test, src/tgbatest/ltl2tgba.cc,
src/tgbatest/ltl2tgba.test, src/tgbatest/ltlprod.cc,
src/tgbatest/ltlprod.test, src/tgbatest/mixprod.cc,
src/tgbatest/mixprod.test, src/tgbatest/powerset.cc,
src/tgbatest/readsave.cc, src/tgbatest/readsave.test,
src/tgbatest/reduccmp.test, src/tgbatest/reductgba.cc,
src/tgbatest/reductgba.test, src/tgbatest/taatgba.cc,
src/tgbatest/tgbaread.cc, src/tgbatest/tgbaread.test,
src/tgbatest/tripprod.cc, src/tgbatest/tripprod.test,
wrap/python/cgi/ltl2tgba.in, wrap/python/tests/ltl2tgba.py,
wrap/python/tests/ltlparse.py, wrap/python/tests/ltlsimple.py:
Fix copyrights.

* src/tgba/taatgba.cc (taa_tgba_formula::~taa_tgba_formula):
Really destroy all formulae, not only half of them.

before doing ++i to avoid memory issues.

* src/tgba/taatgba.cc, src/tgba/taatgba.hh,
src/tgba/tgbaexplicit.cc, src/tgba/tgbaexplicit.hh: Fix them.

* src/ltlast/automatop.cc, src/ltlast/automatop.hh: Rename nfa as
get_nfa to avoid a name clash with the `nfa' class.
* src/ltlvisit/clone.cc, src/ltlvisit/nenoform.cc,
src/ltlvisit/tostring.cc, src/tgbaalgos/eltl2tgba_lacim.cc: Use
get_nfa instead of nfa.
* src/tgba/tgbasafracomplement.cc: Don't use a
const_reverse_iterator.

occuring when labels are pointers.
* src/tgbaalgos/ltl2taa.cc: Fix a bug.
* src/tgbatest/ltl2tgba.cc: Fix a bug.

speed up a little the translation.

* src/tgbaalgos/ltl2taa.cc: Adjust.  Also fix a bug with
acceptance conditions in all_n_tuples.
* src/tgba/taatgba.cc, src/tgba/taatgba.hh: Adjust.

taa_tgba instances labelled by other objects than strings
in the same way Alexandre did for tgba_explicit.

* src/tgba/taatgba.cc, src/tgba/taatgba.hh: Split taa_tgba in two
levels: taa_tgba with no label and taa_tgba_labelled templated by
the type of the label.  Define taa_tgba_string (with the interface
of the former taa_tgba class) and taa_tgba_formula for future use
in ltl2taa.cc.
* src/tgbaalgos/ltl2taa.cc, src/tgbatest/taatgba.cc: Adjust to use
taa_tgba_string.

* src/tgbatest/spotlbtt.test: Use the above function with LaCIM
for ELTL which greatly reduce the size of the automata!

* src/tgba/taa.cc, src/tgba/taa.hh: Rename as ...
* src/tgba/taatgba.cc, src/tgba/taatgba.hh: ... these, and
rename the class taa as taa_tgba.
* src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2taa.hh,
src/tgbaalgos/Makefile.am: Adjust.
* src/tgbatest/ltl2tgba.cc, src/tgbatest/Makefile.am: Adjust.
* src/tgbatest/taa.test: Rename as ...
* src/tgbatest/taatgba.test ... this.
* src/tgbatest/taa.cc: Rename as ...
* src/tgbatest/taatgba.cc ... this, and adjust.

If the input is a tgba_explicit_formula we can output a
tgba_explicit_formula too, and we want to do that because it is
more space efficient.

* src/tgba/tgbaexplicit.hh (get_label): New method.
* src/tgbaalgos/sccfilter.cc (create_transition): New function,
to handle tgba_explicit_formula and tgba_explicit_string output
differently.
(filter_iter): Template it on the output tgba type, and adjust
to call create_transition.
(scc_filter): Use filter_iter<tgba_explicit_formula> or
filter_iter<tgba_explicit_string> depending on the input tgba
type.

A useless acceptance conditions is one that is always implied by
another.

* src/misc/bddop.hh, src/misc/bddop.cc
(compute_neg_acceptance_conditions): New function.
* src/tgba/tgbaexplicit.hh, src/tgba/tgbaexplicit.cc
(set_acceptance_conditions): New function.
* src/tgbaalgos/scc.cc (build_map, build_scc_stats, dump_scc_dot):
Keep track of useful acceptance conditions.
(useful_acc_of): New function.
* src/tgbaalgos/scc.hh (scc_stats, scc_map::scc::useful_scc): New
attributes.
* src/tgbaalgos/sccfilter.cc (filter_iter): Adjust to filter
useless acceptance conditions.
(scc_filter): Compute useful acceptance conditions and pass them
to filter_iter.

* src/tgba/tgbareduc.cc, src/tgba/tgbareduc.hh (prune_scc,
prune_acc, remove_component, compute_scc, remove_acc,
is_not_accepting, delete_scc, is_terminal, remove_scc,
display_scc): Remove anything related to the simplification of
SCCs.

* src/tgbaalgos/ltl2taa.cc: Do NOT use the same bdd_dict for both
the translation and the language containment checker.
* src/tgbatest/spotlbtt.test: Update TAA related tests.

tgba_explicit instances labelled by other objects than strings.

* src/tgba/tgbaexplicit.cc, src/tgba/tgbaexplicit.hh:
Split tgba_explicit in two levels: tgba_explicit with unlabelled
states, and tgba_explicit_labelled templated by the type of
the label.  Define tgba_explicit_string (with the interface
of the former tgba_explicit class) and tgba_explicit_formula
for future use in ltl2tgba.cc.
* src/tgba/tgbareduc.cc, src/tgba/tgbareduc.hh,
src/tgbaalgos/cutscc.cc, src/tgbaalgos/dupexp.cc,
src/tgbaalgos/emptiness.cc, src/tgbaalgos/ltl2tgba_fm.cc,
src/tgbaalgos/powerset.cc, src/tgbaalgos/randomgraph.cc,
src/tgbaparse/public.hh, src/tgbaparse/tgbaparse.yy,
src/tgbatest/explicit.cc, src/tgbatest/ltl2tgba.cc: Adjust to
use tgba_explicit_string when appropriate.

* src/ltlast/formula.cc, src/ltlast/formula.hh (formula::clone):
Transform this static function into a member function.
* src/ltlvisit/destroy.hh (destroy): Document and declare as
deprecated.
* bench/split-product/cutscc.cc, iface/gspn/ltlgspn.cc,
src/eltlparse/eltlparse.yy, src/eltltest/acc.cc,
src/evtgbaalgos/tgba2evtgba.cc, src/evtgbatest/ltl2evtgba.cc,
src/ltlast/automatop.cc, src/ltlast/binop.cc,
src/ltlast/multop.cc, src/ltlast/unop.cc, src/ltlenv/declenv.cc,
src/ltlenv/declenv.hh, src/ltlparse/ltlparse.yy,
src/ltltest/equals.cc, src/ltltest/randltl.cc,
src/ltltest/readltl.cc, src/ltltest/reduc.cc,
src/ltltest/syntimpl.cc, src/ltltest/tostring.cc,
src/ltlvisit/destroy.cc src/ltlvisit/basicreduce.cc,
src/ltlvisit/contain.cc, src/ltlvisit/reduce.cc,
src/ltlvisit/syntimpl.cc, src/tgba/bdddict.cc,
src/tgba/bddprint.cc, src/tgba/taa.cc,
src/tgba/tgbabddconcretefactory.cc, src/tgba/tgbaexplicit.cc,
src/tgba/tgbafromfile.cc, src/tgbaalgos/eltl2tgba_lacim.cc,
src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2tgba_fm.cc,
src/tgbaalgos/ltl2tgba_lacim.cc, src/tgbaalgos/neverclaim.cc,
src/tgbaalgos/randomgraph.cc, src/tgbaparse/tgbaparse.yy,
src/tgbatest/complementation.cc, src/tgbatest/eltl2tgba.cc,
src/tgbatest/ltl2tgba.cc, src/tgbatest/ltlprod.cc,
src/tgbatest/mixprod.cc, src/tgbatest/randtgba.cc,
src/tgbatest/reductgba.cc, wrap/python/cgi/ltl2tgba.in,
wrap/python/tests/ltl2tgba.py, wrap/python/tests/ltlparse.py,
wrap/python/tests/ltlsimple.py: Adjust destroy() usage, and remove
the #include "destroy.hh" when appropriate.

* src/ltlvisit/clone.hh (clone): Document and declare as deprecated.
* src/ltlast/formula_tree.cc, src/ltlvisit/basicreduce.cc,
src/ltlvisit/clone.cc, src/ltlvisit/contain.cc,
src/ltlvisit/lunabbrev.cc, src/ltlvisit/reduce.cc,
src/ltlvisit/syntimpl.cc, src/tgba/bdddict.cc,
src/tgba/formula2bdd.cc, src/tgba/tgbabddconcretefactory.cc,
src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2tgba_fm.cc,
src/tgbatest/complementation.cc, wrap/python/tests/ltlsimple.py:
Adjust clone() usage, and remove the #include "clone.hh" when
appropriate.

in taa_succ_iterator and allow multiple initial states in taa.
* src/tgba/ltl2taa.cc: Remove temporary printing.

constructor.  It does the same thing as the default copy
constructor, and g++ 4.2.3 complained that the copy constructor
of spot::state was not called.  Reported by Denis Poitrenaud.

* src/tgba/taa.cc, src/tgba/taa.hh: taa_succ_iterator is not
on-the-fly anymore allowing some redundant transitions to be
removed. Also a new function to output a TAA.
* src/tgbaalgos/ltl2taa.cc, src/tgbaalgos/ltl2taa.hh: Add the
refined rules from Tauriainen.
* src/tgbatest/ltl2tgba.cc: Use -c to activate refined rules in
ltl_to_taa.
* src/tgbatest/spotlbtt.test: More tests.

* src/tgba/taa.cc, src/tgbaalgos/ltl2taa.cc: Fix style.

* src/misc/bddop.hh, src/tgba/taa.hh, src/tgbaalgos/ltl2taa.hh:
Fix sanity (incorrect include guard).
* src/tgba/tgbacomplement.cc, src/tgba/tgbacomplement.hh:
Copyright 2009.
* src/tgbaalgos/eltl2tgba_lacim.cc: Use abbreviations.
* src/tgbatest/taa.cc: Fix it.

* misc/Makefile.am, misc/bbop.cc, misc/bddop.hh: Factorize some
code on BDDs to compute all_acceptance_conditions from
neg_acceptance_condition.
* src/tgba/Makefile.am, src/tgbatest/Makefile.am: Adjust.
* src/tgba/taa.cc, src/tgba/taa.hh: The TAA class.
* src/tgba/tgbaexplicit.hh: Use the factorized code in bddop.hh.
* src/tgbatest/taa.cc, src/tgbatest/taa.test: Some test cases.