* spot/misc/satsolver.hh: Declare all functions needed.
* spot/misc/satsolver.cc: Implement them.
* spot/twaalgos/dtbasat.cc: Abstract writing.
* spot/twaalgos/dtwasat.cc: Abstract writing.

* .gitignore: Fix typo dt*a instead of dt*ba.

This fix recent failures observed on arch linux because
it uses newer versions of graphviz and Python.

* tests/python/ipnbdoctest.py (sanitize): More substitutions.

* bin/common_setup.cc: Here.

Algorithms that remove transitions can turn a non-deterministic
automaton into a deterministic one, so we need to be able to specify
that determinism can be improved (as opposed to preserved).

* spot/twa/twa.hh (twa::prop_set::improve_det): New attribute.
(twa::prop_keep, twa::prop_copy): Honor it.
* spot/tl/exclusive.cc, spot/twaalgos/alternation.cc,
spot/twaalgos/complete.cc, spot/twaalgos/degen.cc,
spot/twaalgos/determinize.cc, spot/twaalgos/mask.cc,
spot/twaalgos/minimize.cc, spot/twaalgos/remfin.cc,
spot/twaalgos/remprop.cc, spot/twaalgos/sbacc.cc,
spot/twaalgos/sccfilter.cc, spot/twaalgos/simulation.cc,
spot/twaalgos/strength.cc, spot/twaalgos/stutter.cc,
spot/twaalgos/totgba.cc: Adjust calls to prop_keep() and
prop_copy().

* spot/twaalgos/simulation.cc: Reset those to maybe.
* tests/core/semidet.test: Add some tests.

* spot/twa/twa.hh (prop_semi_deterministic): New methods.
* spot/parseaut/parseaut.yy, spot/twaalgos/hoa.cc: Add support for the
semi-deterministic property.
* doc/org/concepts.org, doc/org/hoa.org: Document it.
* spot/twaalgos/isdet.cc,
spot/twaalgos/isdet.hh (is_semi_deterministic): New function.
* bin/autfilt.cc: Add --is-semi-deterministic.
* bin/common_aoutput.cc: Add --check=semi-deterministic.
* tests/core/semidet.test: New file.
* tests/Makefile.am: Add it.
* tests/core/parseaut.test, tests/core/readsave.test: Adjust.

* spot/graph/graph.hh (internal::univ_dest_mapper): New helper class.
* spot/twa/twagraph.cc (merge_univ_dests): Simplify using
univ_dest_mapper.
(purge_unreachable_states, purge_dead_states): Add support for
alternation.
* tests/core/alternating.test: More tests.

* bin/autfilt.cc (ensure_deterministic): Remove alternation on demand.
(process_automaton): Prefer twa::intersects() over
product()/is_empty().
* spot/twa/twa.cc (remove_fin_maybe): Also remove alternation.
* tests/core/alternating.test: More tests.

* bin/autfilt.cc: Implement --is-alternating.
* tests/core/complete.test: Test it.
* NEWS: Mention it.

* bin/autfilt.cc: Implement --is-very-weak.
* tests/core/strength.test: Test it.
* NEWS: Mention it.

and call it after parsing

* spot/twa/twagraph.cc, spot/twa/twagraph.hh
(twa_graph::merge_univ_dests): New method.
* spot/parseaut/parseaut.yy: Call it.
* spot/twaalgos/dot.cc: Improve output, now that
several edges can use the same universal destination.
* tests/core/alternating.test, tests/core/complete.test,
tests/core/parseaut.test, tests/python/_altscc.ipynb,
tests/python/alternating.py, tests/python/alternation.ipynb: Adjust
test case.
* doc/org/tut24.org: Adjust example.

* doc/org/tut23.org, doc/org/tut24.org, doc/org/tut31.org: New files.
* doc/Makefile.am, doc/org/tut.org: Add them.
* doc/org/hoa.org, doc/org/concepts.org: Adjust for alternation support.
* NEWS: Add links.

* spot/twaalgos/remfin.cc: Here.
* tests/core/alternating.test: Add a test case.

* spot/twaalgos/complete.cc: Do not use the initial
state as a sink if it is universal.
* tests/core/complete.test: Add a test case.

* spot/twaalgos/postproc.cc: Call remove_alternation().
* tests/core/alternating.test: Additional test.

* spot/twa/twagraph.hh, spot/twaalgos/are_isomorphic.cc,
spot/twaalgos/canonicalize.cc, spot/twaalgos/couvreurnew.cc,
spot/twaalgos/cycles.cc, spot/twaalgos/degen.cc,
spot/twaalgos/determinize.cc, spot/twaalgos/isunamb.cc,
spot/twaalgos/isweakscc.cc, spot/twaalgos/mask.hh,
spot/twaalgos/minimize.cc, spot/twaalgos/product.cc,
spot/twaalgos/randomize.cc, spot/twaalgos/sbacc.cc,
spot/twaalgos/sccfilter.cc, spot/twaalgos/simulation.cc:
Throw a runtime_error if the input is alternating.

* bin/ltlcross.cc: Add an alternation-removal pass, and
adjust CSV output.
* doc/org/ltlcross.org: Update.
* tests/core/ltl3dra.test, tests/core/ltl3ba.test: Add more tests.
* tests/Makefile.am: Add tests/core/ltl3ba.test.
* NEWS: Mention it.

This is faster than using the abstract interface, and it also supports
alternating automata.  (This will be tested in the tests for
ltlcross's support for alternating automata.)

* spot/twaalgos/stats.cc (stats_reachable, sub_stats_reachable):
Add code specific to twa_graph_ptr.

* spot/twaalgos/remfin.cc (remove_fin_weak): Ignore unreachable
states.  This caused crashes in the test cases for the
upcoming alternation support in ltlcross.

This mixes the subset construction (for 1-state rejecting SCCs) and
the breakpoint construction (for larger rejecting SCCs).  The
algorithm should probably be rewritten in a cleaner and more efficient
way, but that should do for a first version.  It should be easy to
extend it to support Büchi acceptance (since the breakpoint
construction works for this) when we need it.

* spot/twaalgos/alternation.hh,
spot/twaalgos/alternation.cc (remove_alternation): New function.
* tests/python/alternation.ipynb: New file.
* tests/Makefile.am, doc/org/tut.org: Add it.

* spot/twa/twa.hh: Implement the property.
* spot/parseaut/parseaut.yy, spot/twaalgos/hoa.cc: Add input
and output for it.
* spot/twaalgos/strength.cc,
spot/twaalgos/strength.hh (is_very_weak_automaton): New function.
* tests/core/alternating.test: Add a test for --check=strength
on an alternating automaton.
* tests/core/strength.test, tests/core/parseaut.test: Adjust expected
output.
* NEWS, doc/org/hoa.org, doc/org/concepts.org: Document it.

* spot/twaalgos/sccinfo.cc: Consider universal edges as if they were
existential edges.
* spot/twaalgos/sccinfo.hh: Document that.
* spot/twaalgos/dot.cc: Allow option 's' again, for easy testing.
* tests/core/alternating.test: Adjust tests.
* tests/python/_altscc.ipynb: New file (more tests).
* tests/Makefile.am: Add it.

* spot/parseaut/parseaut.yy (fix_initial_state): Use
spot::internal::outgoing_edge_group to reduce all initial states to a
single one.
* tests/core/parseaut.test: Add more tests.

This should will come handy to implement the convertion from LTL to
alternating automata, and to handle automata with multiple initial
states.

* spot/twaalgos/alternation.hh, spot/twaalgos/alternation.cc: New files.
* spot/twaalgos/Makefile.am: Add them.
* python/spot/impl.i: Add bindings.
* tests/python/alternating.py: Test states_and.

The only missing point is that the HOA parser cannot deal with multiple
universal initial states, as seen in parseaut.test.

* spot/graph/graph.hh (new_univ_dests): New function, extracted from...
(new_univ_edge): ... this one.
* spot/twa/twagraph.hh (set_univ_init_state): Implement using
new_univ_dests.
* spot/twaalgos/dot.cc, spot/twaalgos/hoa.cc, python/spot/impl.i:
Add support for universal initial states.
* spot/parseaut/parseaut.yy: Add preliminary support for
universal initial states.  Multiple universal initial states
are still not supported.
* tests/core/alternating.test, tests/core/parseaut.test,
tests/python/alternating.py: Adjust tests and exercise this new feature.

* spot/twaalgos/dot.cc: Handle universal destinations.
Ignore option 's' for alternating automata.
* tests/core/alternating.test: New file.
* tests/Makefile.am: Add it.

Currently this only reads universal branches.  The parser (and the
automaton code) do not support universal initial states.

* spot/parseaut/parseaut.yy: Read universal branches.  Deal with
the no-univ-branch/!univ-branch change in HOA 1.1.
* tests/python/alternating.py: Read the output of print_hoa.
* tests/core/parseaut.test: Adjust test output, and add more tests.

* spot/twaalgos/hoa.cc: Implement it.
* tests/python/alternating.py: Test it.

This only allows creating universal edges, and reading the associated
destinations.

* spot/twa/twagraph.hh (new_univ_edges, univ_dests, is_alternating): New
function.
* python/spot/impl.i: Add Python bindings.
* tests/python/alternating.py: New file.
* tests/Makefile.am: Add it.

* spot/graph/graph.hh: Use the sign bit of destination state X to
designate a universal edge.  Store the destinations of such an edge in a
separate array, at index ~X.
* spot/graph/ngraph.hh, tests/core/graph.cc, tests/core/graph.test,
tests/core/ngraph.cc: Adjust test case to the new interface.

* doc/org/tut22.org: Here.

* doc/org/ltlcross.org: Also fix the documentation of terminal and
weak SCCs.

* doc/org/.dir-locals.el.in, doc/org/init.el.in: Load "shell" instead
of "sh" for recent org-mode version.

* spot/twaalgos/copy.hh: Make a reference to make_twa_graph().

* spot/twaalgos/strength.hh: Add a verb to the descriptions.
Suggested by Alexandre Gbaguidi Aïsse.