Release notes for Vaucanson - LRDE
Contents
1. Tests have shown that using some rational expressions which weight are implemented with double can be potentially dangerous This requires more checks before we can fix it For the moment try to avoid doing that e Rewriting of the minimization_moore algorithm The minimization algorithm named minimization_moore has been rewritten It should be more readable and more reliable now e This version of Vaucanson is released under the GNU Lesser General Public Licence Vaucanson 0 4 October 29 2003 e Addition of an automata I O subsystem e Nearly complete SWIG bindings for algorithms in Vaucanswig e Preliminary documentation for Vaucanswig 11 Addition of a Bitset class which behave almost like a std set lt int gt Addition of a Window class to permit easy text manipulation Addition of a generic search algorithm able to skip characters in the input stream This version of Vaucanson is released under the GNU Lesser General Public Licence Vaucanson 0 3 July 11 2003 More documentation Addition of SWIG modules Vaucanswig Noticeable performance boost thanks to a working unification of references to structural elements This version of Vaucanson is released under the GNU Lesser General Public Licence Vaucanson 0 2 July 02 2003 First public release Rewrite of the fundamental module New graph structure to replace the old legacy ManyLinks implementation Rewrite of most algorithms Implementation of algorithm2. the stream std cout lt lt setpm MODE_ALL lt lt exp lt lt std endl setpm and MODE_ALL are in the vcsn rat namespace To have an exhaustive list of the different manipulators and print modes you may look in vaucanson algebra implementation series rat dump_visitor e tools usual hh was removed A system of context headers is used since vaucanson 0 4 2 and therefore usual hh became useless Furthermore it was a bad idea to use it since it has many includes and may slow a lot a compilation This include has been removed from the distribution if you were using some of its definitions e g usual_automaton_t you now need to use the context headers e g include boolean_automaton hh and use automaton_t in namespace vcsn boolean_automaton You will also find all the macros that may be needed in tools usual_macros hh e This version of Vaucanson is released under the GNU Lesser General Public Licence Vaucanson 0 5 March 24 2004 e New XML Input Output system An XML Input Output system have been added to Vaucanson To use it you will need the Apache Xerces C library version 2 3 To enable the test suite on the XML I O system you need to use the configure option enable xml doc xm1 You can find a minimal documentation here xml DTD and XSL files and some scripts include vaucanson xml Header files src test xml Test files Can be used as examples e Better documentation An effort has been made to mak
3. Release notes for Vaucanson Contact vaucanson lrde epita fr This document describes major updates to the Vaucanson project Vaucanson 1 1 e XML New XML Parser SAX implementation With New XSD Parser doesn t omit transitions with bad label anymore instead of failing e Algorithms eps_removal_sp a Various optimizations e TAF Kit Timer has been improved Intern pipe can now be used vcsn b identity ab xml product b xml is equivalent to vesn b identity ab xml vcsn b product b xml Vaucanson 1 0a June 13th 2007 e Documentation The Doxygen documentation is now installed expanded rather than compressed e Algorithms eps_removal_sp a New generic epsilon_removal algorithm based on shortest_path minimize a Various optimizations transpose a Transition labels are now transposed too image a b and domain a b they replace output_projection and input_projection These algorithms work for both FMP transducers and RW transducers e XML Bug fixes I O optimizations e Utilities Lib VCSN Provides C libraries for the main automaton types SWIG Fix compilation issues e TAF Kit The option bench relies on iterations of report time to benchmark the algorithms Vaucanson 1 0 July 28th 2006 e XML Many bug fixes for instance the alphabet is no longer filled with the default range if it is said to be empty Nodes like lt l
4. abel_type gt are renamed to lt labelType gt so as to conform to XSD coding style VCSN_XSD_PATH is no longer used The environment variable VCSN_DATA_PATH should point to the Vaucanson data directory containing among others the vaucan son xsd file vaucanson xsd is no longer looked for in the current directory transcode s Overloaded function Convert a std string respectively a char into XML e TAF kit The new binaries vesn z and vcsn tdc are toolkit to work with Z automata and FMP trans ducers Many commands algorithms have been added in vcsn b e Algorithms is_ambiguous a Test if a is ambiguous trim_here a Trim the automaton a sub_normalize_here a Sub normalized the automaton a invert t Return the inverse of the RW transducer t i e the transducer that performs the invert rational relation uwcompose a Composition for boolean transducers that keeps the same number of paths e Renaming and minor additions Support operator simplifies the writing for one letter supports Instead of e supp begin write e supp The closure functions were renamed as eps_removal since that s what they actually do The macros for_each are now called for_all normalized_composition functions are now called compose The automaton library is installed with make install e Layout The layout of the sources was changed to match the layout of Vaucanson w
5. csn xml automaton_t a new_automaton alphabet_t std cin gt gt automaton_loader a io string_out xml XML To dump automaton as an XML document do include lt vaucanson tools xml_dump hh gt tools xml_dump std cout a A name Or use the automaton_saver function e Big cleaning in the graph implementation A lot of superfluous operations were done in the former implementation Cleaning the code provided huge performance improvement The actual implementation has the same interface than the former one e Update context headers More granularity has been added to context headers To create one you need to include desired files from the include vaucanson contexts directory in a specific order Please refer to the sources for more details e A long standing bug in the core of the library was corrected Until now some compiler optimisation that was believed to happen did not happen Because of this all Element instances had an overhead of at least a few bytes in their memory footprint while in most cases it was not necessary The code was rewritten to allow for this expected optimisation e This version of Vaucanson is released under the GNU Lesser General Public Licence Vaucanson 0 6 1 October 26 2004 e Vaucanson works with GNU C 3 2 3 3 3 4 and ICC 8 1 e Vaucanswig is no longer enabled by default To enable the compilation of Vaucanswig run configure enable vaucanswig Be warned thi
6. e the Doxygen documentation look better The documentation is still incomplete and some errors probably remain but it should be far more usable now Especially the Algorithm section of the documentation should now be exhaustive e Instantiation of Element which set is dynamic may fail when you do not specify the set To get more safety at runtime trying to instantiate an Element which set is dynamic without initializing the set will fail at compile time This ensures every Element you will manipulate has its corresponding set associated This has two consequences Using Element set should provoke no more segmentation faults or similar undesired behavior The bound method has no sense anymore and therefore has been removed If you make calls to this method in your programs just consider it returns true every time now and remove the call 10 e Many renamings To get a more consistent interface a few methods have changed Consequently your old code designed for Vaucanson 0 4 may not work properly with Vaucanson 0 5 However converting it to the new nomenclature should be straightforward All names containing the word serie are now written with series instead For example serie_get is now series_get All serie_t typedefs are now series_elt_t The method value_get for the elements of series is now called get The method value_set for the elements of series is now called ass
7. ere were also some fixes in the standard_of algorithm and derived_term_automaton now works with expressions that have right weights The closure was rewritten and should be faster now Beside from the algorithms a big bug was fixed in the algebra core of Vaucanson which used to cause some problems when one wanted to use different alphabets in different automata in the same program Also rational expressions which weights are implemented as floats or doubles now work correctly e verbalize is deprecated use expand A new expand function was created It performs a simple expansion of a rational expression For example expand a a b aatab expand a atb aata b expand a a atb aata atb expand at a atb a aatab To use this function include vaucanson algorithms krat_exp_expand hh and call the vcsn expand function on an Element lt Series rat exp lt M W gt gt or a rat_exp_t if you are using a con text While this function behave exactly as verbalize on series which have a finite support the latter is deprecated It will probably be removed in next releases e krat_exp_print does not exist anymore The file vaucanson algorithms krat_exp_print hh was removed To print a rational expression with no extra parenthesis just use the lt lt operator onto a C stream std cout lt lt exp lt lt std endl To make this operator behave as in previous versions send the right format onto
8. erived Term automaton algorithm has been added Two heuristics for state elimination method algorithm have been added src demos directory has been rearranged algorithms Contains demos of small algorithms automaton_library Contains binaries that generate XML samples of various automata function_library Contains binaries that call common algorithms available in the library for most of the available predefined types B Z R Z min Z max transducers realtime transducers transducers one_rule_rewriting Fibonnaci and One Rule Rewriting demonstration utilities vgrep grep demonstration Some bugs were fixed to ensure library stability Mainly algorithms Moore minimization sub normalized composition realtime and projection were fixed Context headers now include by default all standard algorithms All deprecated documentation has been removed e XML proposal has been changed and some documentation added As an example Boolean automaton that recognize a b is described as follows lt automaton gt lt content gt lt states gt lt state name s0 gt lt states gt lt transitions gt lt transition src s0O dst s0 label a gt lt transition src s0O dst s0 label b gt lt initial state s0 gt lt final state s0 gt lt automaton gt Note that now lt initial gt and lt final gt are children of lt transitions gt and the lt initials gt and lt finals gt tag a
9. habet_t automaton_t and rat_exp_t respectively for alphabets automata and rational expressions For transducers you will get the following extra types ALGEBRAIC SETS ELEMENTS OF SET LOW LEVEL IMPLEMEN TATIONS output_semiring t output_semiring_elt_t output_semiring_elt_value_t ALGEBRAIC SETS ELEMENTS OF SET LOW LEVEL IMPLEMEND TATIONS output_series_set_t output_series_set_elt_t output_series_set_elt_value_t In addition to that a context provides the user with the following functions automaton_t new_automaton alphabet_t Create an empty automaton rat_exp_t new_rat_exp alphabet_t Create an empty rational expres sion rat_exp_t new_rat_exp alphabet_t std string Create a rational expression and initial ize it Ex new_rat_exp a atb automaton_t standard_of rat_exp_t Build the standard automa ton of an exp automaton_t thompson_of rat_exp_t Build the thompson automa ton of an exp rat_exp_t aut_to_exp automaton_t Build an exp from an automaton If you want more algorithms just browse the vaucanson algorithms directory or look in the HTML documentation Currently the following contexts are available boolean_automaton z_automaton r_automaton Z_max_plus Z_min_plus boolean_transducer e Many bug fixes As usual many bugs were fixed Especially the quotient should be correct now Th
10. hen installed vaucanson xsd is now is the data directory The automaton library is now split by type See data b and data z The generators used there are nice demo programs VaucanSWIG is at the top level demos utilities has been moved into demos e This release was made and coordinated by Akim Demaille Florent Terrones Guillaume Lazzara Guillaume Leroi Jacques Sakarovitch Matthieu Varin Micha l Cadilhac Robert Bigaignon Sylvain Lombardy Vaucanson 0 8 May 15 2006 TAF Kit The Typed Automata Function Kit of Vaucanson TAF Kit This is a packaging through binary programs of the main algorithms of Vaucanson In this release only the Boolean semiring is supported See the related documentation for help Documentation A first user s manual for TAF Kit has been introduced The Doxygen documentation has been reworked XML system The XSD file has been extended to express transitions as XML trees The XML proposal has been completly reworked The XSD file path can now be set by either the environment variable or the CPP macro VCSN_XSD_PATH It is also automatically checked in the share directory where this file would be installed on make install Renaming The following renaming have been made edge is now transition new_ functions are now make_ origin of and src_of are now aim_of and dst_of for_each loops have been changed to for_a
11. ll for consistency with STL for_each that uses functor Delta functions Delta functions used to extract the successor states or edges of a state can now take functor with the deltaf methods of an automaton If the operator of the functor returns Booleans and an application of the functor returns false the loop over all successors is stopped Benchmarks Some Vaucanson benchmarks were added to the distribution Feel free to make your bench results and please send us them Bug fixes Many bugs have been fixed in the core library and some algorithms have been cleaned This release was made and coordinated by Akim Demaille Florent Terrones Guillaume Lazzara Guillaume Leroi Jacques Sakarovitch Matthieu Varin Michael Cadilhac Robert Bigaignon Sylvain Lombardy Vaucanson 0 7 2 November 9 2005 e Vaucanson works with GNU C 3 3 3 4 4 0 and ICC 9 0 e Compliance with GCC 4 0 and ICC 9 0 Vaucanson is compliant with the latest version of GCC and ICC and was successfully tested on Linux and MacOs e Bug fixes Some bugs were fixed in the core library and in the XML system e XML system The system now handles geometric attributes in Vaucanson automata See product algorithm for a sample use Vaucanson 0 7 1 June 25 2005 More algorithms on transducers seen as automata over a direct product of free monoid are avail able evaluation composition covering composition co covering intersection A Broken D
12. oc The convenience files vaucanson_ hh in the include vaucanson directory have been stripped from their leading vaucanson_ hopcroft_minimization hh is now named minimization_hopcroft hh to be consistent with minimization_moore hh e New implementation for numerical semirings It is now possible to use rational numbers as an implementation in numerical semirings In order to do so the header lt vaucanson algebra concrete semiring rational_number hh gt must be included All you need to do then is to declare a variable as follows vcesn Element lt semiring_t vcsn algebra RationalNumber gt q num denom semiring_t can be any numerical semiring The usual operators have been overloaded and you can get the integer or double value of the fraction by using to_int or to_double You can also access the numerator with num and denominator with denom e Many more tests The test suite has been extended and improved Generic tests are now instantiated on many more types Also existing tests have been enriched with extra checks and non existing tests have been written Some bugs have been discovered fixed and now have their corresponding regression test As aresult running make check should take more time than before but now trusting a successful check sequence is less hazardous Note that it is still possible to disable some tests by removing the test directory and running the configure script again
13. re removed From now on all files compliant with the previous XML proposal are not compliant with the new proposal e This version of Vaucanson is released under the GNU General Public Licence Vaucanson 0 7 May 17 2005 e Vaucanson works with GNU C 3 2 3 3 3 4 and ICC 8 1 e Transducers seen as automata over a free monoid product are now available Until now transducers in Vaucanson could only be seen as automata with multiplicity in a series It is now possible to manipulate transducers seen as automata over a free monoid product Two context headers have been written fmp_transducer and z_fmp_ransducer fmp stands for Free Monoid Product which can be used in the same way as previous context headers On top of the classical types defined in all context headers they define several types needed when manipulating this type of transducers ALGEBRAIC SETS ELEMENTS OF SET LOW LEVEL IMPLE MENTATIONS first_alphabet_t second_alphabet_t first_monoid_t first_monoid_elt_t first_monoid_elt_value_t second_monoid_t second_monoid_elt_t second_monoid_elt_value_t In addition to that the contexts provide the user with the following functions Create an empty automaton automaton_t new_automaton first_alphabet_t second_alphabet_t Create a couple of words that can directly be given to add_series_edge for instance series_set_elt_t make_couple first_alphabet_t second_alphabet_t std st
14. ring std string Some new algorithms have also been added fmp_to_realtime and realtime_to_fmp Enables the user to switch from one view of transducers to another normalized_composition Enables the composition of normalized and sub normalized transducers seen as automata over a free monoid product edges with labels of types a b 1 a and a 1 e New XML I O system The former XML system based on a DTD grammar was replaced by a system based on XSD schema specification The new system is backward compatible with old XML documents just change namespace reference to http vaucanson 1lrde epita fr and remove DTD node This new specification comes with full transducer support and a set of default types for both automata and transducer To declare a transducer on free monoid product do as the following lt transducer xmlns http vaucanson 1rde epita fr gt lt content gt lt states gt lt state name s0 gt lt states gt lt transitions gt lt transition src s0 dst s0 in a out b gt lt transitions gt lt initials gt lt finals gt lt transducer gt To load an automaton for example on Z semiring from a stream containing the XML document do as the following include lt vaucanson xm1 XML hh gt include lt vaucanson z_automaton hh gt using namespace vcsn using namespace vcsn z_automaton using namespace v
15. s compilation takes several hours on a modern computer e The demos in src demos xm1 were updated The demo formerly named algorithms is now compiled for various semirings under the following names b Boolean semiring z usual semiring on Z r usual semiring on R z_max_plus tropical semiring with max on Z z_min_plus tropical semiring with min on Z Furthermore additional algorithms may be called from this demo transpose and eval A list of states may be provided to the aut_to_exp algorithm thus allowing the elimination of states to be performed in a specified order An additional src demo xm1 samples directory was created with some XML samples and some programs that can generate XML samples e expand definitively replaces verbalize The verbalize function does not exist anymore It is replaced by expand which was intro duced in Vaucanson 0 6 A short description of expand can be found below in the description of Vaucanson 0 6 e This version of Vaucanson is released under the GNU Lesser General Public Licence Vaucanson 0 6 July 18 2004 e Big cleanings in Vaucanson XML A big work was done around Vaucanson XML which should be fairly more usable now To save an automaton in a XML representation just include vaucanson xml static hh and do stream lt lt vcsn automaton_saver auto vesn io string_out vesn xml xml_loader To reload the automaton you may do the opposite operation
16. s on rational expressions Initial Doxygen documentation efforts This version of Vaucanson is released under the GNU Lesser General Public Licence Vaucanson 0 1 January 2002 Initial release This version of Vaucanson is released under the GNU Lesser General Public Licence 12
17. stream gt gt vcsn automaton_loader auto vesn io string_out vesn xml xml_loader Of course if you want to get rid of vcsn io vcsn xml1 etc you may do using namespace vcsn xml using namespace vcsn io Many more examples and utilities can be found in the directory src demos xml Just browse the sources Few more examples A few programs were written for the CIAA 2004 conference It is not an extraordinary or complex code but it demonstrates how quick and easy it may be to use Vaucanson for assembling some algorithms and building simple automata It may also be a good introduction to learn Vaucanson by practice These examples are in src demos ciaa New features in context headers A new context header for automata over the tropical semiring with the min and operators was added Furthermore some new functions and typedefs are declared in each header If you want to use the context foo then include vaucanson foo hh You will get the following types in the namespace vcsn foo ALGEBRAIC SETS ELEMENTS OF SET LOW LEVEL IMPLE MENTATIONS alphabet_t letter_t monoid_t monoid_elt_t monoid_elt_value_t semiring_t semiring_elt_t semiring_elt_value_t series_set_t series_set_elt_t series_set_elt_value_t automata_set_t automaton_t automaton impl t series_set_t rat_exp_t rat_exp_impLt As the user you will probably only be interested in alp
Download Pdf Manuals
Related Search