Also generalize the degen-lcache option.

* src/tgbaalgos/postproc.cc, src/tgbaalgos/postproc.hh: Add the option.
* src/bin/spot-x.cc: Document it.
* src/tgbaalgos/degen.cc, src/tgbaalgos/degen.hh: Implement it.
* src/tgbatest/ltlcross2.test: Add a test configuration.
* src/tgbatest/degenlskip.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add degenlskip.test.

* src/bin/ltlcross.cc: Fix it.
* src/tgbatest/ltlcross3.test: New file.
* src/tgbatest/Makefile.am: Add it.
* NEWS: Mention it.

* NEWS: Mention it.
* doc/org/ltlcross.org: Document it.
* src/bin/ltlcross.cc: Implement it.
* src/tgbatest/Makefile.am, src/tgbatest/defs.in,
src/tgbatest/ltlcross4.test: Test it.

* src/misc/satsolver.cc, src/misc/satsolver.hh (satsolver_get_solution):
New function, that accepts a solution split on multiple 'v ' lines.
* src/tgbaalgos/dtbasat.cc, src/tgbaalgos/dtgbasat.cc (get_solution):
Remove, and adjust existing code to use satsolver_get_solution().
* src/tgbatest/readsat.cc, src/tgbatest/readsat.test: New files.
* src/tgbatest/Makefile.am: Add them.
* src/bin/man/spot-x.x: Mention the SAT competition rules for
the expected input/output format.

* src/tgbatest/satmin.test: New file.
* src/tgbatest/Makefile.am: Add it.

* src/tgbaalgos/dbacomp.cc: Here.
* src/tgbaalgos/dbacomp.hh: Adjust documentation.
* src/tgbatest/dbacomp.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add it.
* src/tgbatest/det.test: Update.

* src/tgbaalgos/postproc.cc: Use tba_determinize_check()
if option "tba-det" is set.
* src/tgbaalgos/postproc.hh (tba_determinize_): New attribute.
* src/tgbatest/det.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add it.

* src/bin/dstar2tgba.cc, src/bin/man/dstar2tgba.x: New files.
* src/bin/Makefile.am, src/bin/man/Makefile.am: Add them.
* NEWS: Mention it.
* src/bin/ltl2tgba.cc, src/tgbaalgos/stats.cc, doc/org/ltl2tgba.org:
Rename the %S sequence as %c, for consistency with dstar2tgba.
* src/tgbatest/ltl2dstar.test: Add more tests.
* src/tgbatest/ltl2dstar2.test: New file.
* src/tgbatest/Makefile.am: Add it.

* src/tgba/tgbamask.cc, src/tgba/tgbamask.hh,
src/tgba/tgbaproxy.cc, src/tgba/tgbaproxy.hh: New files.
* src/tgba/Makefile.am: Add them.
* src/tgbatest/explicit3.cc, src/tgbatest/explicit3.test:
New files.
* src/tgbatest/Makefile.am: Add them.

* src/bin/ltlcross.cc: Add support for %D.
* src/bin/man/ltlcross.x: Add example.
* NEWS: Mention it.
* src/tgbatest/ltl2dstar.test: New file.
* src/tgbatest/Makefile.am: Add it.

Supports reading Rabin and Streett automata, and converting them to
nondeterministic Büchi automata (for Rabin) or TGBA (for Streett).

* src/dstarparse/Makefile.am, src/dstarparse/dstarparse.yy,
src/dstarparse/dstarscan.ll, src/dstarparse/fmterror.cc,
src/dstarparse/parsedecl.hh, src/dstarparse/public.hh,
src/dstarparse/nra2nba.cc, src/dstarparse/nsa2tgba.cc: New files.
* configure.ac, src/Makefile.am, README: Adjust.
* src/tgbatest/ltl2tgba.cc: Add options -XD, -XDB.
* src/tgbatest/dstar.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add it.

* src/misc/bitvect.cc, src/misc/bitvect.hh: New files.
* src/misc/Makefile.am: Add them.
* src/tgbatest/bitvect.cc, src/tgbatest/bitvect.test: New files.
* src/tgbatest/Makefile.am: Add them.

* src/tgbaalgos/word.cc, src/tgbaalgos/word.hh: New files.
* src/tgbaalgos/Makefile.am: Add them.
* src/tgbatest/ltlcrossce.test: New file.
* src/tgbatest/Makefile.am: Add it.
* src/bin/ltlcross.cc: Compute and display an accepted word
for nonempty cross-products.
* NEWS, doc/org/ltlcross.org: Document it.

* src/tgbaalgos/simulation.hh, src/tgbaalgos/simulation.cc
(simulation_sba, cosimulation_sba, iterated_simulations_sba): New
function.  Also speedup the existing functions by avoiding
add_acceptince_conditions() and add_conditions().  Finally, use
scc_filter_states() when dealing with degeneralized automata.
* src/tgbaalgos/postproc.cc, src/tgbaalgos/postproc.hh (do_ba_simul):
New method.  Use it after degeneralization.
* src/tgba/tgbaexplicit.hh (get_transition, get_state): New methods.
* src/tgbatest/basimul.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add it.
* NEWS: Introduce the new function and summarize the bug.

* src/tgbaalgos/simulation.cc: Attempt to fix several cases.
* src/tgbatest/sim.test: Add more tests.
* src/tgbatest/sim2.test: New file.
* src/tgbatest/Makefile.am: Add it.

Thomas Badie authored Sep 27, 2012 and Alexandre Duret-Lutz committed Apr 09, 2013

* src/tgba/bddprint.cc, src/tgba/bddprint.hh: Add bdd_print_isop
that prints the bdd into a Irreductible Sum Of Product.
* src/tgbaalgos/dupexp.cc, src/tgbaalgos/dupexp.hh: Add a way to
know which states (in the input) is which (in the result).
* src/tgbaalgos/simulation.cc, src/tgbaalgos/simulation.hh: Add
the Don't Care Simulation and the Don't Care Iterated Simulation.
* src/tgbatest/ltl2tgba.cc, src/tgbatest/spotlbtt.test,
src/tgbatest/Makefile.am, src/tgbatest/sim.test: Test them.
* bench/ltl2tgba/algorithms, bench/ltl2tgba/README,
bench/ltl2tgba/algorithms: Add a way to bench the don't care
simulation.

* src/tgbatest/ltl2neverclaim.test: Rename as...
* src/tgbatest/ltl2neverclaim-lbtt.test: ... this.
* src/tgbatest/ltl2neverclaim.test: New version, using ltlcross.
* src/tgbatest/Makefile.am: Add ltl2neverclaim-lbtt.test.

Thomas Badie authored Nov 13, 2012 and Alexandre Duret-Lutz committed Nov 14, 2012

* src/tgbaalgos/simulation.cc: Fix non determinism.
* src/tgbatest/simdet.test: Test that the behavior is now correct.
* src/tgbatest/Makefile.am (TESTS): Add the new test to the
test-suite.

* src/bin/ltlcheck.cc, src/bin/man/ltlcheck.x,
src/tgbatest/ltlcheck.test, src/tgbatest/ltlcheck2.test: Rename as ...
* src/bin/ltlcross.cc, src/bin/man/ltlcross.x,
src/tgbatest/ltlcross.test, src/tgbatest/ltlcross2.test: ... these.
* NEWS, src/bin/Makefile.am, src/bin/man/Makefile.am,
src/tgbatest/Makefile.am: Adjust.

* src/tgbatest/ltlcheck.test, src/tgbatest/ltlcheck2.test: New files.
* src/tgbatest/Makefile.am: Add them.

* src/tgbaalgos/lbtt.hh, src/tgbaalgos/lbtt.cc (lbtt_parse):
New function.
* src/tgba/tgbaexplicit.hh (get_acceptance_condition): Make it public.
* src/tgbatest/ltl2tgba.cc: Add a -XL option to read LBTT file.
* src/tgbatest/lbttparse.test: New file.
* src/tgbatest/Makefile.am: Add it.

* NEWS: Mention this.
* COPYING: Replace by GPL v3.
* src/sanity/style.test: Check files with the wrong license,
in case we forgot to update it during a merge.
* Makefile.am, bench/Makefile.am, bench/emptchk/Makefile.am,
bench/emptchk/defs.in, bench/emptchk/ltl-human.sh,
bench/emptchk/ltl-random.sh, bench/emptchk/pml-clserv.sh,
bench/emptchk/pml-eeaean.sh, bench/emptchk/pml2tgba.pl,
bench/ltl2tgba/big, bench/ltl2tgba/defs.in, bench/ltl2tgba/known,
bench/ltl2tgba/lbtt2csv.pl, bench/ltl2tgba/ltl2baw.in,
bench/ltl2tgba/parseout.pl, bench/ltl2tgba/small,
bench/ltlclasses/Makefile.am, bench/ltlclasses/defs.in,
bench/ltlclasses/run, bench/ltlcounter/Makefile.am,
bench/ltlcounter/defs.in, bench/ltlcounter/run,
bench/scc-stats/Makefile.am, bench/scc-stats/stats.cc,
bench/split-product/Makefile.am, bench/split-product/cutscc.cc,
bench/split-product/pml2tgba.pl, bench/wdba/Makefile.am,
bench/wdba/defs.in, bench/wdba/run, configure.ac, doc/Makefile.am,
doc/dot.in, doc/tl/Makefile.am, ifac...

Reported by Étienne Renault.

* src/tgbaalgos/isdet.cc (is_deterministic): Invert return code.
* src/tgbatest/nondet.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add it.

Thomas Badie authored Sep 26, 2012 and Alexandre Duret-Lutz committed Sep 27, 2012

* src/tgbatest/renault.test: New file.
* src/tgbatest/Makefile.am: Add it.
* src/tgbaalgos/simulation.cc: Fix the bug.

* src/tgbaalgos/cycles.cc, src/tgbaalgos/cycles.hh,
src/tgbatest/cycles.test: New files.
* src/tgbaalgos/Makefile.am, src/tgbatest/Makefile.am: Add them.
* src/tgbatest/ltl2tgba.cc: Add a -KC option for testing.

* src/tgbaalgos/postproc.cc, src/tgbaalgos/postproc.hh: New class to
capture the postprocessing logic.
* src/tgbaalgos/Makefile.am: Add them.
* src/bin/ltl2tgba.cc, src/bin/man/ltl2tgba.x: New files.
* src/bin/Makefile.am, src/bin/man/Makefile.am: Add them.
* src/tgbatest/spotlbtt.test: Prune the list of configurations slightly.
* src/tgbatest/spotlbtt2.test: New file.
* src/tgbatest/Makefile.am: Add it.
* bench/ltl2tgba/algorithms, bench/ltl2tgba/defs.in: Adjust to
use the new binary.
* NEWS: Update.

* src/tgbatest/ltl2ta.test: Adjust expected values.
* src/tgbatest/Makefile.am (TESTS): Add ltl2ta.test.

* src/tgbatest/randpsl.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add it.

This implementation of direct simulation was only working on
degeneralized automata, and produce automata that are inferiors to
those output by the new direct simulation implementation (in
tgba/simulation.hh) which can also work on TGBA.  The delayed
simulation has never been reliable.  It's time for some spring
cleaning.

* src/tgba/tgbareduc.hh, src/tgba/tgbareduc.cc: Delete.
* src/tgba/Makefile.am: Adjust.
* src/tgbaalgos/reductgba_sim.cc, src/tgbaalgos/reductgba_sim.hh:
Remove all code, and keep only a deprecated replacement
from reduc_tgba_sim().
* src/tgbaalgos/reductgba_sim_del.cc: Delete.
* src/tgbaalgos/Makefile.am: Adjust.
* src/tgbatest/reduccmp.test, src/tgbatest/reductgba.cc,
src/tgbatest/reductgba.test: Delete.
* src/tgbatest/Makefile.am: Adjust.
* src/tgbatest/ltl2tgba.cc: Undocument options -R1s, -R1t,
-R2s, -R2t, and implement them using the new direct simulation.
Remove options -Rd and -RD.
* src/tgbatest/spotlbtt.test: Remove entry using these old options.
* wrap/python/spot.i: Do not process tgbaalgos/reductgba_sim.cc.

* src/tgbatest/explicit2.test: New file.
* src/tgbatest/Makefile.am: Add it.
* src/tgbatest/explicit2.cc: Print the LTL formula as text.

Pierre PARUTTO authored Mar 06, 2012 and Alexandre Duret-Lutz committed Apr 12, 2012

* src/tgba/tgbaexplicit.hh, src/tgba/tgbaexplicit.cc: Factor most of
the code in an explicit_graph<State, Type> that inherits from type.
The tgba_explicit type<State> now inherits from
explicit_graph<State,tgba>.
* src/ltlvisit/contain.cc, src/neverparse/neverclaimparse.yy
src/tgba/tgbareduc.cc, src/tgba/tgbareduc.hh, src/tgbaalgos/cutscc.cc,
src/tgbaalgos/dupexp.cc, src/tgbaalgos/dupexp.hh,
src/tgbaalgos/emptiness.cc, src/tgbaalgos/ltl2tgba_fm.cc,
src/tgbaalgos/ltl2tgba_fm.hh, src/tgbaalgos/minimize.cc,
src/tgbaalgos/powerset.cc, src/tgbaalgos/randomgraph.cc,
src/tgbaalgos/sccfilter.cc, src/tgbaparse/tgbaparse.yy,
src/tgbatest/complementation.cc, src/tgbatest/explicit.cc,
src/tgbatest/explprod.cc, src/tgbatest/ltl2tgba.cc,
src/tgbatest/mixprod.cc, src/tgbatest/powerset.cc,
src/tgbatest/tgbaread.cc, src/tgbatest/tripprod.cc:
Replace tgba_explicit* by the actual type used.
* src/tgbatest/explicit2.cc: New file.
* src/tgbatest/Makefile.am: Add it.

* src/tgbaalgos/minimize.cc (minimize_wdba): Fix the Löding
algorithm to use colors.  The previous implementation was an
incorrect approximation.
* src/tgbatest/wdba2.test: New file showing two equivalent
formulas that were minimized in automata with different sizes.
* src/tgbatest/Makefile.am: Add it.

* iface/dve2/Makefile.am, src/eltlparse/Makefile.am
src/eltltest/Makefile.am, src/evtgba/Makefile.am,
src/evtgbaalgos/Makefile.am, src/evtgbaparse/Makefile.am,
src/evtgbatest/Makefile.am, src/kripke/Makefile.am,
src/kripketest/Makefile.am, src/ltlast/Makefile.am,
src/ltlparse/Makefile.am, src/ltltest/Makefile.am,
src/ltlvisit/Makefile.am, src/misc/Makefile.am,
src/neverparse/Makefile.am, src/saba/Makefile.am,
src/sabaalgos/Makefile.am, src/sanity/Makefile.am,
src/tgba/Makefile.am, src/tgbaalgos/Makefile.am,
src/tgbaalgos/gtec/Makefile.am, src/tgbaparse/Makefile.am,
src/tgbatest/Makefile.am, wrap/python/Makefile.am (AM_CPPFLAGS):
Make sure $(top_builddir)/src is included.

There is no point in degeneralizing an automaton if it can be WDBA
minimized.  Doing so will only augment the number of states and
slow down the powerset construction used by the WDBA minimization.

* src/tgbatest/babiak.test: New file.  It includes 5 formulae
which Tomáš Babiak reported Spot 0.7.1 would take over one hour to
translate if degeneralization and WDBA minimization were both
requested.
* src/tgbatest/Makefile.am (TESTS): Add it.
* src/tgbatest/ltl2tgba.cc: Do WDBA minimization before
degeneralization.  The above formulae are now all translated in a
few seconds.

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.

states).

* src/tgbaalgos/tgbatba.cc: When degeneralizing to SBA, remove the
acceptance conditions that are common to all outgoing transitions
of this state.  This helps to make the degeneralization
idempotent.
* src/tgbatest/degenid.test: New test case.
* src/tgbatest/Makefile.am: Add it.

Reported by Tomáš Babiak <xbabiak@fi.muni.cz>.

* src/tgba/tgbatba.cc (tgba_tba_proxy): Replace the std::map used
to record outgoing transitions by an Sgi::hash_map, and keep the
order of these transitions in a separate list.
* src/tgbatest/degendet.test: New file.
* src/tgbatest/Makefile.am (TESTS): Add it.
* THANKS: Add Tomáš and convert to utf8.

generate these formulae with "genltl".

* src/tgbatest/ltlcounter/: Remove this directory.
* src/tgbatest/Makefile.am: Adjust.
* src/tgbatest/ltlcounter.test, bench/ltlcounter/run: Use genltl
to generate the formulae.
* bench/ltlcounter/README: Do not mention src/tgbatest/ltlcounter/
anymore.

* src/misc/intvcmp2.cc, src/misc/intvcmp2.hh: New files.
* src/misc/Makefile.am: Add them.
* src/tgbatest/intvcmp2.cc: New test.
* src/tgbatest/Makefile.am: Add it.
* src/tgbatest/intvcomp.test: Call it.