This patch offers several new algorithms on transducers seen as
	automata over a free monoid product. Some projections are now
	available: 'domain' which creates an automaton which transitions
	are labeled by the first component of each word of the fmp
	transducer, 'image' which does the same with the second component
	and 'identity' which transforms an automaton in a fmp transducer
	by creating, for each word, a pair containing twice this word.
	Furthermore, evaluation is now available and a new function has
	been added to the fmp context headers in order to facilitate the
	call to the evaluation algorithm, just as it is already done for
	transducers.

	* include/vaucanson/algorithms/projections_fmp.hh,
	* include/vaucanson/algorithms/projections_fmp.hxx: New. Add 'domain',
	'image' and 'identity' projections for fmp transducers.
	* include/vaucanson/algorithms/evaluation_fmp.hh,
	* include/vaucanson/algorithms/evaluation_fmp.hxx: New. Add an
	evaluation algorithm for fmp transducers.
	* include/Makefile.am: Update accordingly.

	* src/tests/automata/algos/fmp_transducers/evaluation_fmp_test.hh: New.
	Write a test for the evaluation on fmp transducers.
	* src/tests/automata/algos/fmp_transducers/Makefile.am: Update
	accordingly.

	* include/vaucanson/contexts/fmp_transducer_functions.thh,
	* include/vaucanson/contexts/fmp_transducer_functions.thxx: Add the
	'evaluation' function to ease the interface with the user.

	* include/vaucanson/algorithms/aut_to_exp.hxx: As  the  user would
	like  to  precise her  own  seed,  remove  the  automated  one  in
	RandomChooser's constructor.

	* src/benchs/derived_terms/derived_terms_bench.hh: Print edges
	number.

	* src/benchs/minimization_nd: Remove.
	* src/benchs/minimization_nd/minimization_nd_bench.hh: Remove.
	* src/benchs/minimization_nd/Makefile.bench: Remove. This bench
	has been removed as it's redundant seeing `derived_term' bench.
	* src/benchs/Makefile.am,
	* src/benchs/generate_all_benchs.sh,
	* configure.ac: Update accordingly.

	* include/vaucanson/algorithms/normalized_composition.hxx: Remove
	useless included file.

	* include/vaucanson/algorithms/outsplitting.hh,
	* include/vaucanson/algorithms/outsplitting.hxx: Add wrappers to
        outsplitting and insplitting functions.

	* src/tests/automata/algos/fmp_transducers/normalized_composition_test.hh:
	Fix a small bug.

	* src/benchs/minimization_2n/minimization_2n_brzozowski_bench.hh: New.
	* src/benchs/minimization_debruijn/minimization_debruijn_brzozowski_bench.hh: New.
	* src/benchs/minimization_2n/Makefile.bench,
	* src/benchs/minimization_debruijn/Makefile.bench: Add the Brzozowski
	minimization to be benched.

	* src/benchs/common/bench_constructs.hh: Remove the binary automaton
	C_1 construction as it's implemented in quotient_*_bench.hh.

	* src/benchs/quotient/quotient_bool_bench.hh: New.
	* src/benchs/quotient/quotient_bench.hh: Remove.
	* src/benchs/quotient/quotient_z_bench.hh: New.
	* src/benchs/quotient/Makefile.bench: Bench the quotient
	on the C_1 automaton (as described in Inside Vaucanson),
	for both boolean and Z automata.
	

	* src/benchs/derived_terms/derived_terms_dt_bench.hh: Remove.
	* src/benchs/derived_terms/derived_terms_bench.hh: New.
	* src/benchs/derived_terms/derived_terms_so_bench.hh: Remove.
	* src/benchs/derived_terms/Makefile.bench: Derived terms bench
	now does both derivatives_automaton and standard_of.

	* src/benchs/composition/realtime_composition_bench.hh,
	* src/benchs/composition/normalized_composition_bench.hh,
	* src/benchs/composition/Makefile.bench: Change input of this
	bench to be a(b)^n and b(a)^n.

	* include/vaucanson/algorithms/aut_to_exp.hxx: Fix use of
	`srand': use it only once in the lifetime of a RandomChooser.

	* include/vaucanson/algorithms/realtime_to_fmp.hxx: Fix
	use of support. Copy them before their use.

	* include/vaucanson/algorithms/normalized_composition.hxx,
	* include/vaucanson/algorithms/outsplitting.hxx: Fix small problems in
	composition of fmp transducers.

	* src/benchs/composition/realtime_composition_bench.hh,
	* src/benchs/composition/normalized_composition_bench.hh: New. Add
	bench for fmp transducer composition.
	* src/benchs/composition/Makefile.bench,
	* src/benchs/generate_all_benchs.sh,
	* configure.ac: Update accordingly.

	* src/benchs/determinization/Makefile.bench: Change \$1 to \$$1.

	* src/benchs/derived_terms/Makefile.bench,
	* src/benchs/minimization_debruijn/Makefile.bench,
	* src/benchs/minimization_2n/Makefile.bench,
	* src/benchs/determinization/Makefile.bench: Set interval of bench.
	* src/benchs/minimization_nd/minimization_nd_bench.hh,
	* src/benchs/derived_terms/derived_terms_dt_bench.hh,
	* src/benchs/derived_terms/derived_terms_so_bench.hh: Change output.
	Be more verbose.
	* src/benchs/Makefile.am: Change the order of bench. The Stroppa's
	bench is the last one as it's more likely to fail.

	* bootstrap.sh: Add the bootstrapping of bench files.

	* src/benchs: New. Bench suite directory.
	* src/benchs/generate_benchs.sh: New.   This script  generates .cc
	files associated  with _bench.hh files,  and creates corresponding
	Makefile.am's.
	* src/benchs/generate_all_benchs.sh:  New.   Wrapper    that  call
	generate_benchs.sh for all bench directories.
	
	* src/benchs/minimization_stroppa/minimization_bench_fsm.cc,
	* src/benchs/minimization_stroppa/usual.hxx,
	* src/benchs/minimization_stroppa/init.hh,
	* src/benchs/minimization_stroppa/fsm_minimize.hh,
	* src/benchs/minimization_stroppa/tools.hxx,
	* src/benchs/minimization_stroppa/data,
	* src/benchs/minimization_stroppa/init.hxx,
	* src/benchs/minimization_stroppa/Makefile.bench,
	* src/benchs/minimization_stroppa/minimization_bench_moore.cc,
	* src/benchs/minimization_stroppa/int_traits.hh,
	* src/benchs/minimization_stroppa/minimization_bench_hopcroft.cc,
	* src/benchs/minimization_stroppa/tools.hh,
	* src/benchs/minimization_stroppa/usual_ana_predefs.hh,
	* src/benchs/minimization_stroppa:   New.  A   minimization  bench
	thanks to Nicolas Stroppa.

	* src/benchs/determinization/determinization_bench.hh,
	* src/benchs/determinization/Makefile.bench,
	* src/benchs/determinization/determinization_bench_fsm.cc,
	* src/benchs/determinization: New. A  bench which determinize an n
	states automaton to a 2^n automaton.

	* src/benchs/minimization_2n/minimization_2n_moore_bench.hh,
	* src/benchs/minimization_2n/minimization_2n_hopcroft_bench.hh,
	* src/benchs/minimization_2n/Makefile.bench,
	* src/benchs/minimization_2n: New.  A   minimization bench  on the
	resulting automaton of the determinization previously described.

	* src/benchs/quotient/quotient_bench.hh,
	* src/benchs/quotient/Makefile.bench,
	* src/benchs/quotient: New. A quotient bench.
	
	* src/benchs/minimization_nd/minimization_nd_bench.hh,
	* src/benchs/minimization_nd/Makefile.bench,
	* src/benchs/minimization_nd:  New.  A  minimization bench  over a
	nondeterministic automaton.
	
	* src/benchs/minimization_debruijn/minimization_debruijn_moore_bench.hh,
	* src/benchs/minimization_debruijn/minimization_debruijn_hopcroft_bench.hh,
	* src/benchs/minimization_debruijn/Makefile.bench,
	* src/benchs/minimization_debruijn: New. A minimization bench over
	the De Bruijn automaton, thanks to Sylvain Lombardy.

	* src/benchs/derived_terms/derived_terms_dt_bench.hh,
	* src/benchs/derived_terms/derived_terms_so_bench.hh,
	* src/benchs/derived_terms/Makefile.bench,
	* src/benchs/derived_terms:  New. A bench  to compare consequences
	of the `derived terms' algorithm, and the `standard_of' one.

	* src/benchs/common/alpha.syms: New. Alpha mapping for FSM.
	* src/benchs/common/algorithm.hh: New. Algorithm used in benchs.
	* src/benchs/common/bench_automaton.hh: New. The `bench_automaton'
	is   a   light    automaton   with   `label_are_letters'   and   a
	`small_alpha_letter'.
	* src/benchs/common/bench_constructs.hh:   New.   Basic  automaton
	constructions used in the benchs.
	* src/benchs/common/Makefile.flags,
	* src/benchs/common/Makefile.am,
	* src/benchs/common: New.
	
	* src/benchs/Makefile.am: New. Define a `bench' rule and subdirs.
	* src/Makefile.am: Add `bench' as a subdir.
	* configure.ac: Add Makefiles in src/bench to be generated.
	* Makefile.am: Add a `bench' rule.

	* include/vaucanson/tools/bencher.hh: Add macros to bench silently
	and just have the numerical value of the bench.

	* include/vaucanson/automata/implementation/graph.hxx (op_letter_delta):
	Don't name the `delta_kind' nor the structure to avoid a warning.

	* include/vaucanson/z_transducer.hh: New. Add a context header for
	transducers on Z semiring.
	* include/Makefile.am: Update accordingly.

	* include/vaucanson/contexts/fmp_transducer_functions.thh,
	* include/vaucanson/contexts/fmp_transducer_functions.thxx: Modify
	'make_couple' function to return a monoid_elt_t instead of a
	series_elt_t.
	* src/tests/context_headers/fmp_transducers/global_consistency_test.hh:
	Update accordingly.

	* src/tests/test-suites/context_headers_z_transducer.defs: New.
	Instantiate a test for the new context header.
	* src/tests/test-suites/z_transducer.defs: New. Instantiate a test on
	transducers on Z semiring.

	* src/tests/test-suites/z_fmp_transducer.defs: New. Instantiate a test
	on fmp transducers on Z semiring.
	* src/tests/test-suites/generate-all.sh: Update accordingly.

	* src/tests/automata/algos/fmp_transducers/instantiation_test.hh:
	Remove useless test.
	* src/tests/automata/algos/fmp_transducers/Makefile.am: Update
	accordingly.

	* include/vaucanson/algorithms/sub_normalize.hh,
	* include/vaucanson/algorithms/sub_normalize.hxx: Minor fix.

2005-05-27  Florent Terrones  <florent.terrones@lrde.epita.fr>
	
	* include/vaucanson/xml/XML.hh: Add the attribute 'name_' to the
	structure 'XML' so as to store the automaton name during the XML
	session.
	* include/vaucanson/tools/xml_dump.hxx: Add the name of the automaton
	in 'xml_dump'.
	* include/vaucanson/tools/xml_load.hh,
	* include/vaucanson/tools/xml_load.hxx: New. Add 'xml_load' tool to
	fill an automaton from a IStream containing XML	data.
	* include/Makefile.am: Update accordingly.

	* include/Makefile.am: Add missing files.

	* include/vaucanson/xml/tools.hxx: Fix a bug with boolean automata.
	* src/tests/xml/b_ref.dot: Update accordingly.

	* include/vaucanson/algorithms/sub_normalize.hh,
	* include/vaucanson/algorithms/sub_normalize.hxx: New. Add 
	sub-normalization for FMP transducers.

	* src/tests/automata/algos/fmp_transducers/sub_normalize_test.hh: New.
	Add test for sub-normalization of FMP transducers.

2005-05-25  Florent Terrones  <florent.terrones@lrde.epita.fr>

        * include/vaucanson/algorithms/internal/partial_rat_exp.hxx:
        Fix a compilation error that happens if one uses derivatives_automaton
        with the DEBUG flag.

	This patch aim to make the test suite only output printable
	characters.
	In case of error in a test, relevant informations are now output
	in a file in `/tmp'.
	* src/tests/check/tester.hh: Add `TEST_FAIL_SAVE' macro for
	test to save informations about failing tests in a file. Force
	`EQTEST' to only output printable characters through the
	filtering function `printable'.
	* src/tests/automata/algos/label_aware_graphs/glushkov_test.hh,
	* src/tests/automata/algos/label_aware_graphs/sum_test.hh,
	* src/tests/automata/algos/label_aware_graphs/concat_test.hh,
	* src/tests/automata/algos/label_aware_graphs/closure_test.hh,
	* src/tests/automata/algos/label_aware_graphs/in_concat_test.hh,
	* src/tests/automata/algos/graphs/accessible_test.hh,
	* src/tests/automata/algos/boolean_automata/complete_test.hh,
	* src/tests/automata/algos/labeled_graphs/thompson_test.hh,
	* src/tests/automata/algos/labeled_graphs/elimination_test.hh,
	* src/tests/automata/algos/letter_combination_labeled_graphs/product_regression_test.hh,
	* src/tests/automata/algos/letter_combination_labeled_graphs/product_test.hh,
	* src/tests/algebra/series/krat/boolean/krat_exp_cderivation_linear_test.hh,
	* src/tests/algebra/series/krat/main/krat_exp_parse_test.hh,
	* src/tests/algebra/series/krat/main/krat_exp_flatten_test.hh,
	* src/tests/algebra/series/krat/main/krat_exp_expand_test.hh,
	* src/tests/algebra/series/krat/main/krat_exp_constant_term_test.hh,
	* src/tests/algebra/series/krat/main/krat_exp_linearize_structure_test.hh,
	* src/tests/algebra/series/krat/main/krat_exp_linearize_test.hh,
	* src/tests/algebra/series/krat/main/krat_exp_aci_canonical_test.hh,
	* src/tests/algebra/series/krat/derivations/derivations_common.hh,
	* src/tests/algebra/series/misc/series_test.hh,
	* src/tests/algebra/numerical_semiring/numerical_semiring_test.hh,
	* src/tests/misc/assert_test.cc,
	* src/tests/misc/random.cc,
	* src/tests/misc/limits.cc: Fix the output of these tests, forcing
	it to be clean by only printing printable characters.
	* src/tests/algebra/series/krat/main/krat_exp_derivation_test.hh:
	Remove. This test is useless as
	`src/tests/algebra/series/krat/derivations/derivation/*' do the
	same, in a more complete way.	
	* src/tests/algebra/series/krat/main/Makefile.am: Update accordingly.

	* include/vaucanson/algebra/implementation/series/rat/star_height_visitor.hh,
	* include/vaucanson/algebra/implementation/series/rat/star_height_visitor.hxx:
	New. Add a new visitor that computes the star height of an expression.

	* include/vaucanson/algebra/implementation/series/rat/length_visitor.hh,
	* include/vaucanson/algebra/implementation/series/rat/length_visitor.hxx:
	New. Add a new visitor that computes the length of an expression,
	i.e. the number of letters in the expression.

	* include/vaucanson/algebra/implementation/series/rat/exp.hxx,
	* include/vaucanson/algebra/implementation/series/rat/exp.hh:
	Add star_height() and length() methods to class exp.

	* include/Makefile.am:
	Update accordingly.

	* include/vaucanson/algorithms/aut_to_exp.hxx:
	Add a new chooser that chooses randomly states to delete.

        * include/vaucanson/algebra/implementation/series/polynoms.hxx: 
        Fix bug introduced by the use of 'assertion_()'.

        Cosmetic changes, as suggested by Thomas Claveirole.

        * include/vaucanson/algebra/implementation/series/krat_exp_support.hxx: 
        Change 'unreachable' to 'result_not_computable'.

        * include/vaucanson/misc/contract.hh: Replace '__trap' with
        'vcsn_trap_' to avoid using names reserved by the standard
        library.

        * include/vaucanson/algebra/implementation/series/polynoms.hxx:
        Fix spelling error.

        Fix long-standing bug that prevented the correct optimization of
        static Element structures. Thank Nicolas Stroppa for this report. 

        * include/vaucanson/algebra/implementation/series/polynoms.hh,
        * include/vaucanson/algebra/implementation/series/krat.hh,
        * include/vaucanson/algebra/implementation/alphabets/decorated_alphabet.hh,
        * include/vaucanson/algebra/implementation/alphabets/set_alphabet.hh:
        Replace 'dynamic_values' with 'dynamic_value'.

        Make more parts of Vaucanson compile with -fno-exceptions. Clean
        use of contract macros.

        Now uses of 'result_not_computable' will abort() the program
        unless EXCEPTION_TRAPS is defined. (this is what EXCEPTION_TRAPS
        stands for in the first place).

        * include/vaucanson/misc/contract.hh: Always define
        vcsn::contract::trap. Add macro 'result_not_computable_if'. Change
        'result_not_computable' to look more like other contract
        macros. Add 'assertion_', 'precondition_' and 'postcondition_' to
        accept an explanation message. Add 'unreachable' macro to detect
        unreachable code.

        * include/vaucanson/algorithms/closure.hxx: Use
        'result_not_computable_if()'.

        * include/vaucanson/algebra/concept/freemonoid_base.hxx: Use
        'precondition_()' instead of direct throw.

        * include/vaucanson/algebra/implementation/semiring/rational_number.hxx:
        Use 'postcondition()' instead of direct throw.

        * include/vaucanson/algebra/implementation/series/polynoms.hxx:
        Use 'postcondition()' instead of direct throw.

        * include/vaucanson/algebra/implementation/series/krat_exp_parser.hh:
        Report dependency on exceptions in the documentation.

        * include/vaucanson/algebra/implementation/series/krat_exp_parser.hxx:
        Use 'unreachable' to beautify.

        * include/vaucanson/algebra/implementation/series/krat_exp_support.hxx: 
        Use 'unreachable' to beautify and express error message more verbosely.

        * include/vaucanson/contexts/automaton_functions.thxx: Use
        'postcondition_()' instead of direct throw.

        * include/vaucanson/algebra/implementation/semiring/numerical_semiring.hxx:
        Use 'assertion_' to beautify.

        * include/vaucanson/algebra/implementation/series/polynoms.hxx:
        Use 'assertion_' to simplify. (this change also optimizes one test
        away when VCSN_NDEBUG is defined)

        * include/vaucanson/algebra/implementation/series/transpose.hxx, 
        * include/vaucanson/algebra/implementation/series/krat.hxx, 
        * include/vaucanson/algebra/concept/semiring_base.hxx, 
        * include/vaucanson/algebra/concept/series_base.hxx: Use
        'pure_service_call' instead of 'assertion', because it is what it
        was intended for in the first place.

        * src/tests/algebra/numerical_semiring/numerical_semiring_test.hh:
        Change exception test accordingly.

	* include/vaucanson/algorithms/minimization_moore.hxx: Add the
	include to `delta_kind.hh'.

	
	* include/vaucanson/algebra/concept/freemonoid_base.hxx:
	Replace unsigned int with bool to avoid a possible bug.

	* include/vaucanson/algorithms/minimization_moore.hh,
	* include/vaucanson/algorithms/minimization_moore.hxx: Debug
	`minimization_moore' with non letter transitions, making sort of
	`cut_up' on the fly. Add a `co_minimization_moore' algorithm,
	making a co-minimization on a co-deterministic automaton.
	* src/tests/automata/algos/boolean_automata/minimization_test.hh:
	Add `co_minimization_moore' test.

	* configure.ac: Bump to Vaucanson 0.7.
	* doc/NEWS.txt: Update with Vaucanson new features.

	* include/vaucanson/xml/tools.hxx: Fix label creation for automata.

	* src/demos/xml/samples/div3base2.xml,
	* src/demos/xml/samples/c1.xml,
	* src/demos/xml/samples/occ_b.xml,
	* src/demos/xml/samples/lomb1.xml,
	* src/demos/xml/samples/lomb2.xml,
	* src/demos/xml/samples/double_ring6.xml,
	* src/tests/xml/b_ref.xml: Update reference files.

	* include/vaucanson/xml/tools.hxx: Fix label creation for automata.

	* include/vaucanson/algorithms/transducer_to_fmp.hh,
	* include/vaucanson/algorithms/transducer_to_fmp.hxx: Rename to...
	* include/vaucanson/algorithms/realtime_to_fmp.hh,
	* include/vaucanson/algorithms/realtime_to_fmp.hxx: ...These. 
	Rename algorithm trans_to_fmp to realtime_to_fmp.

	* include/vaucanson/algorithms/fmp_to_transducer.hh,
	* include/vaucanson/algorithms/fmp_to_transducer.hxx: Rename to...
	* include/vaucanson/algorithms/fmp_to_realtime.hh,
	* include/vaucanson/algorithms/fmp_to_realtime.hxx: ...These. 
	Rename algorithm fmp_to_trans to fmp_to_realtime. 

	* src/tests/automata/algos/fmp_transducers/normalized_composition_test.hh,
	* include/Makefile.am: Update accordingly.

	* include/vaucanson/algorithms/cut_up.hxx: Fix error in algorithm.