The Vcsners are proud to announce the release of Vcsn 2.5, aka the k-lightest release! Vcsn is a platform dedicated to the computation of, and with, finite state machines. It provides an efficient C++ library, a Python interface, and a graphical user interface on top of IPython. Noteworthy changes include: - two new implementations to compute the k-lightest paths (aka "best" paths: with the smallest weights) in tropical automata. - several new demos showing how to use the C++ library, including a translator from (French) text messages (aka SMS) into French. - a new means for the users to configure Vcsn. This adds a new prerequisite to build Vcsn: libyaml-cpp. - a much better and faster caching system of runtime generated C++ code. Users of dyn (and therefore of Python) should note an improved amortization of the compilation costs. - several portability issues reported by users were fixed. For more information, please, see the detailed news below. People who worked on this release: - Akim Demaille - Clément Démoulins - Clément Gillard - Sarasvati Moutoucomarapoulé - Sébastien Piat - Younes Khoudli For more information, please visit http://vcsn.lrde.epita.fr, in particular https://vcsn.lrde.epita.fr/Vcsn2.5. Packages of Vcsn 2.5 should appear soon on various distributions (MacPorts, Debian, ArchLinux, Docker Hub). Vcsn 2.5 is also available online, at http://vcsn-sandbox.lrde.epita.fr. ## 2017-01-23 ### Improved error messages Parse errors were improved with caret-style reports for expressions and automata in dot (Graphviz) and daut syntax. In [5]: vcsn.Q.expression('<1/2>a + <1/0>b') RuntimeError: 1.10-14: Q: null denominator <1/2>a + <1/0>b ^^^^^ while reading expression: <1/2>a + <1/0>b In [6]: vcsn.automaton(''' ...: $ -> 0 ...: 0 -> 1 <1/2>a, b ...: 1 -> $''') RuntimeError: 3.1-16: B: unexpected trailing characters: /2 while reading: 1/2 while reading: <1/2>a, b 0 -> 1 <1/2>a, b ^^^^^^^^^^^^^^^^ while reading automaton In [7]: vcsn.automaton('digraph{vcsn_context="lal, b" 0->1[label="<2>a"]}') RuntimeError: 1.35-48: B: invalid value: 2 while reading: 2 while reading: <2>a digraph{vcsn_context="lal, b" 0->1[label="<2>a"]} ^^^^^^^^^^^^^^ while reading automaton ## 2017-01-14 ### "auto" automaton file format Pass "auto" to read_automaton (in dyn, static, Python or the Tools) to let the system guess the automaton file format (daut, dot, etc.). ## 2017-01-11 ### Sms2fr New Natural Language Processing demonstration of the computations of the lightest paths. This application is a translator from SMS (i.e., text messages) to proper French. The implementation is based on _Rewriting the orthography of SMS messages_, François Yvon, In Natural Language Engineering, volume 16, 2010. The translator uses pre-trained automata and through compositions with the automaton representing the text message, generates all possible translations of the word. The best solution is then found with a shortest path algorithm. An example is given in the `Sms2fr.ipynb` notebook. ## 2017-01-01 ### A richer dyn The `vcsn::dyn` API was enriched. All the dyn types now support the usual operators: comparisons (`==`, `!=`, `<`, `<=`, `>`, `>=`), and compositions (`+`, `*`, `&`). New functions facilitate the creation of `dyn` values from strings (`make_word`, etc.). The file `tests/demos/operators.cc` shows several examples, explained in the `C++-Library.ipynb` notebook. For instance: // A simple automaton. auto a1 = make_automaton("context = lal, q\n" "$ 0 <1/2>\n" "0 1 <2>a, <6>b\n" "1 $\n", "daut"); // Its context. auto ctx = context_of(a1); // Evaluate it. assert(evaluate(a1, make_word(ctx, "a")) == make_weight(ctx, "1")); assert(evaluate(a1, make_word(ctx, "b")) == make_weight(ctx, "3")); // Concatenate to itself. auto a2 = a1 * a1; assert(evaluate(a2, make_word(ctx, "ab")) == make_weight(ctx, "3")); // Self-conjunction, aka "power 2". auto a3 = a1 & a1; assert(evaluate(a3, make_word(ctx, "b")) == make_weight(ctx, "9")); ## 2016-12-25 ### Configuration Vcsn now supports configuration files. They will be used to provide users with a means to customize Vcsn, for instance to tune the graphical rendering of the automata, to tailor the display of expressions, etc. For a start, it provides a simple means to get the configuration information, including from Vcsn Tools. $ vcsn ipython --no-banner In [1]: import vcsn In [2]: vcsn.config('configuration.cxxflags') Out[2]: '-Qunused-arguments -O3 -g -std=c++1z' $ vcsn configuration configuration.cxxflags -Qunused-arguments -O3 -g -std=c++1z This adds a new dependency: libyaml-cpp. Beware that version 0.5.2 is buggy and will not work properly. Use 0.5.1, or 0.5.3 or more recent. ## 2016-12-20 ### compare: new algorithm Three-way comparison is now available in all the layers, as `compare`, for automata, expressions, labels, polynomials and weights. This is used in Python to implement the comparisons (`<`, `<=`, `>`, `=>`, `==`, `!=`) of expressions, and of automata (`<`, `<=`, `>`, `=>`). However, since the comparison on automata is performed on the _list_ of transitions, automata that are "very much alike" (i.e., different only by superficial details) will be considered different, so `==` and `!=` are still using a safer, but much slower, comparison. In [2]: exp = vcsn.Q.expression In [3]: exp('a').compare(exp('b')) Out[3]: -1 In [4]: exp('a').compare(exp('a')) Out[4]: 0 In [5]: exp('<3>a').compare(exp('a')) Out[5]: 1 ## 2016-12-12 ### k shortest paths algorithms Two algorithms for searching k shortest paths in graphs have been implemented: "Eppstein" and "Yen". Hence, we can now search for the k lightest (smallest with respect to weights, aka "best" paths) paths in an automaton through the "lightest" algorithm. "lightest" used to compute these paths with an inefficient heap-based implementation: aut.lightest(5) aut.lightest(5, "auto") Note that "auto" does not use the latter algorithm when returning only one path, as simpler shortest path algorithms would apply to the situation and be more efficient. It then uses Dijkstra's algorithm. It can now be called with the given Yen and Eppstein algorithms as follows: aut.lightest(5, "eppstein") aut.lightest(5, "yen") Yen's algorithm requires the given automaton to have no cycles, while Eppstein supports any type of automaton. For small values of k, Yen's algorithm has better performances than Eppstein, but with increasing values of k, Eppstein is always more efficient.