NEWS.md 187 KB
Newer Older
Akim Demaille's avatar
Akim Demaille committed
1
2
3
4
![Vcsn Logo](share/vcsn/figs/vcsn.png)

Vcsn Release Notes
==================
5
6

This file describes user visible changes in the course of the development of
7
8
Vcsn, in reverse chronological order.  On occasions, significant changes in
the internal API may also be documented.
9

Akim Demaille's avatar
Akim Demaille committed
10
11
# Vcsn 2.8 (2018-05-08)

Akim Demaille's avatar
Akim Demaille committed
12
13
14
15
We are happy to announce the release of Vcsn 2.8, a bug fix release.

For more information see the detailed news below.

Akim Demaille's avatar
Akim Demaille committed
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
## New Features
### vcsn diagnose: check that Vcsn is properly installed
This tool runs a few commands to check that Vcsn works properly.  It
generates diagnostics that help the Vcsn team understand problems on the
user side.

## Bug Fixes
### Spontaneous transitions in literal automata
In literal automata, transitions without explicit label were accepted but
misinterpreted.  For instance in this automaton in Daut:

    context = lao, q
    $ 0 <2>
    0 1 <3>
    1 $ <4>

the pre- and post-transitions have no label, but are weighted (by 2 and 4).
The inner transition between states 0 and 1 should be labeled with `\e` (and
be weighted by 3).  Unfortunately the user was expected to make the `\e`
explicit:

    context = lao, q
    $ 0 <2>
    0 1 <3>\e
    1 $ <4>

otherwise unexpected results would be yielded (for instance the first
automaton was considered proper).

Now, missing labels are interpreted as the empty word, and both
specifications above denote the same automaton.

----------------------------------------------------------------------

Akim Demaille's avatar
Akim Demaille committed
50
51
52
53
54
55
56
# Vcsn 2.7 (2018-03-25)

We are happy to announce the release of Vcsn 2.7.  This is mostly a bug fix
release, with improvements in the documentation, based on user feedback.
Most of our efforts are currently devoted to Vcsn 3.0.

For more information see the detailed news below.
57

58
## New features
Akim Demaille's avatar
Akim Demaille committed
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
### Improved compatibility between single- and multitape expressions
The automatic promotion from single-tape to multitape is more general.  For
instance:

    In [2]: c = vcsn.context('lat<lan, lan>, b')

    In [3]: c.expression('a')
    Out[3]: a|a

    In [4]: c.expression('a*b* @ (ab)*')
    Out[4]: (a|a)*(b|b)*@((a|a)(b|b))*

    In [5]: c.expression('a*b* @ (ab)*').shortest(10)
    Out[5]: \e|\e + ab|ab

74
75
76
77
78
79
### vcsn doc is a new tool
Run `vcsn doc automaton.determinize`, or `vcsn doc Automata`, etc.  The
special shortcuts `vcsn doc` opens the Read-me-first notebook, and `vcsn doc
index` leads to Algorithms, the page that lists the existing documentation
of algorithms (`automata.determinize`, etc.).

Akim Demaille's avatar
Akim Demaille committed
80
81
82
83
84
85
### Compressed efsm files
Vcsn can read efsm files compressed with bzip2 and xz.  In some extreme
cases, the xz-compressed file can be 5% of the original file.

The files for the sms2fr demo are now compressed with xz.

86
87
88
89
### vcsn score has several new options
The command `vcsn score` benchmarks Vcsn.  Its output can be processed with
`vcsn score-compare` to see the trends in performances between versions.

Akim Demaille's avatar
Akim Demaille committed
90
91
92
93
94
95
96
97
98
99
100
Benchmarks are now numbered, to give a hint of the progress:

    $ vcsn score
    vcsn version: 2.6-085-g6dcae17ef
      1/116  0.25s : a.is_proper()      # a = "", 1000000x
      2/116  0.11s : b.format("text")   # b = [abc] -> B, 100000x
      3/116  0.35s : b.expression(e)    # e = [ab]{20000}, 1000x
    ...
    115/116  0.75s : a.weight_series()  # a = std(a{12000}+<1>[b-z]{12000}), c = [a-z] -> Nmin, 200x
    116/116  0.89s : a.weight_series()  # a = std([a-z]{200}), c = [a-z] -> Z, 10x

101
The new option `-o`/`--output` allows to specify the output file name.
102

103
104
Better yet: option `-d`/`--dir` specifies the directory in which the score
file is saved; its name will be forged from `git describe`, something like
105
106
107
108
`v2.5-050-g01dbf326`.  Such names are interpreted by `vcsn score-compare` to
relate the benches to the git commit title.  Both features need that you run
these commands from a git repository of Vcsn.

109
110
111
112
Option `-j`/`--job` allows to run the benchmarks concurrently.  This can be
very useful to "warm" vcsn (have it compile the needed algorithms), or to
get a nice approximation of the actual benches, however, sticking to a
single bench at a time is recommended to get faithful measurements.
Akim Demaille's avatar
Akim Demaille committed
113

Akim Demaille's avatar
Akim Demaille committed
114
115
116
117
118
119
120
121
Option `-l`/`--list` lists the benches without running them.

Option `-s`/`--sort` sorts the benchmarks before running them.

### Documentation
Several errors were fixed.  The page `expression.compose.ipynb` is new.

### Examples of C++
Akim Demaille's avatar
Akim Demaille committed
122
123
The directories `tests/demo` and `tests/benchmarks` contain more examples
using the Vcsn C++ library.
Akim Demaille's avatar
Akim Demaille committed
124

Akim Demaille's avatar
Akim Demaille committed
125
126
127
128
129
130
131
132
## Bug fixes
### Incorrect order for 8bit characters
Calling `compare` on labels would lead to surprising results with 8bit
characters (seen as negative ints).  This resulted in the incorrect display
of the expression `[\x01-\xfe]` as `[\x80-\xfe] + [\x01-\x7f]`.

Both are fixed, and 1 is less than 254 again.

Akim Demaille's avatar
Akim Demaille committed
133
----------------------------------------------------------------------
134

Akim Demaille's avatar
Akim Demaille committed
135
136
137
138
139
140
141
# Vcsn 2.6 (2017-11-13)

The Vcsn team is happy to announce the long overdue release of Vcsn 2.6.
Most of our work was devoted to providing a better, smoother, user
experience.  This includes improvements in the build system, better
performances, extended consistency, and more legible error messages.
Multitape expressions also received a lot of attention.
Akim Demaille's avatar
Akim Demaille committed
142

Akim Demaille's avatar
Akim Demaille committed
143
For more information see the detailed news below.
Akim Demaille's avatar
Akim Demaille committed
144
145
146

We warmly thank our users who made valuable feedback (read "bug reports"):
Victor Miller, Dominique Soudière and Harald Schilly.  Dominique and Harald
Akim Demaille's avatar
Akim Demaille committed
147
helped integrating Vcsn into CoCalc (formerly SageMathCloud).
Akim Demaille's avatar
Akim Demaille committed
148
149
150
151
152
153
154
155

People who contributed to this release:

- Akim Demaille
- Clément Démoulins
- Clément Gillard
- Sarasvati Moutoucomarapoulé

Akim Demaille's avatar
Akim Demaille committed
156
## New features
Akim Demaille's avatar
Akim Demaille committed
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
### Promotion from single to multitape
It is now possible to mix single-tape expressions with multitape
expressions.  This is especially handy when using labels classes (`[abc]`).
For instance:

    In [2]: zmin2 = vcsn.context('lat<lan, lan>, zmin')

    In [3]: zmin2.expression(r'([ab] + ⟨1⟩(\e|[ab] + [ab]|\e))*')
    Out[3]: (a|a+b|b+<1>(\e|(a+b)+(a+b)|\e))*

is a easy means to specify an expression generating an automaton that
computes the edit-distance (between words or languages).  Or, with a wide
alphabet:

    In [4]: zmin = vcsn.context('lan(a-z), zmin')

    In [5]: zmin2 = zmin | zmin

    In [6]: zmin2
    Out[6]: {abcdefghijklmnopqrstuvwxyz}? x {abcdefghijklmnopqrstuvwxyz}? -> Zmin

    In [7]: zmin2.expression(r'([^] + ⟨1⟩(\e|[^] + [^]|\e))*')

In the future the display of expressions will also exploit this approach.

### vcsn compile now links with precompiled contexts
If you write a program using dyn::, then it will benefit from all the
precompiled algorithms.

Akim Demaille's avatar
Akim Demaille committed
186
### vcsn compile now supports --debug
187
188
189
Use this to avoid the removal of intermediate object files.  On some
platforms, such as macOS, the object file contains the debug symbols, so
their removal makes the use of a debug harder.
Akim Demaille's avatar
Akim Demaille committed
190
191
192
193
194
195
196
197
198

### vcsn compile now uses -rpath
Programs/libraries generated by `vcsn compile` needed to be told where the
Vcsn libraries were installed.  In practice, it meant that `vcsn run` was
needed to execute this program, and in some situations it was not even
sufficient.

Now, `vcsn compile my-prog.cc` generates `my-prog` which can be run directly.

Akim Demaille's avatar
Akim Demaille committed
199
### random_expression supports the tuple operator
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
It is now possible to generate multitape expressions such as `(a|x*)*`.
Before, random_expression was limited to expressions on multitape labels
such as `(a|x)*`.

    In [1]: import vcsn

    In [2]: c = vcsn.context('lan(abc), q')

    In [3]: c2 = c | c

    In [4]: for i in range(10):
       ...:     e = c2.random_expression('|, +, ., *=.2, w.=.2, w="min=-2, max=2"', length=10)
       ...:     print('{:u}'.format(e))
       ...:
    a|a+(ε|b)*+⟨1/2⟩ε|ε
    (ε+c)a|(⟨2⟩ε+c)
    (ε|b+(c|a)*)*
    ε|a+a|b
    c|b+⟨2⟩ε|(ε+b)
    ε|a+((a|ε)(ε|b)(ε|c))*(b|ε)
    (a|b+c|ε)(a|b)
    ε*|ε
    ε+a|a+⟨2⟩(b|ε)
    (ε+ε*)|ε

Akim Demaille's avatar
Akim Demaille committed
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
Generating expressions with compose operators is also supported.

    In [5]: for i in range(10):
       ...:     e = c2.random_expression('|=.5, +, ., @=2', length=10, identities='none')
       ...:     print('{:u}'.format(e))
       ...:
    ((b|ε)ε)(ε(ε|a))
    ε(ε|c)+((ε|a)(a|b)+ε|c)
    ((ε|a)(ε|b))((b|a)(c|c)@b|b)
    (b|b@ε+a|b)@(c|ε@b|ε)
    (ε+ε|a)@(ε|c@ε|a+b|ε)
    (ε|a+ε|c)((ε|b)(c|ε))
    (a|ε)((ε+c)|(a+ε))
    c|ε@(a|ε)(ε|b@b|ε)
    (ε+ε|b)@ε|b+ε|a
    b(ε²)|((ε+ε)+a)

### New algorithms
A few algorithms were added:

  - context.compose

    Composing `{abc} x {xyz}` with `{xyz} x {ABC}` gives, of course,
    `{abc} x {ABC}`.

  - expansion.normalize, expansion.determinize

    These are rather low-level features.  The latter is used internally when
    derived-term is asked for a deterministic automaton.

  - expansion.expression

    The "projection" of an expansion as an expression.

  - label.compose

    For instance `a|b|x @ x|c` -> `a|b|c`.

  - polynomial.compose

    Additive extension of monomial composition.  For instance composing
    `a|e|x + a|e|y + a|e|\e` with `x|E|A + y|E|A + \e|E|A` gives
    `<3>a|e|E|A`.

  - polynomial.shuffle and polynomial.infiltrate

Akim Demaille's avatar
Akim Demaille committed
271
    The missing siblings of polynomial.conjunction.
Akim Demaille's avatar
Akim Demaille committed
272

273
274
275
### Doxygen is no longer needed
By default, `make install` generated and installed the C++ API documentation
using Doxygen.  It is now disabled by default, pass `--enable-doxygen` to
Akim Demaille's avatar
Akim Demaille committed
276
`configure` to restore it.
277

278
## Bug Fixes
279
### Severe performance regression when reading daut
Akim Demaille's avatar
Akim Demaille committed
280
281
Version 2.5 introduced a large penalty when reading daut files, especially
large ones.
282

283
### Tupling of automata could be wrong on weights
284
285
As a consequence, `expression.inductive` was also producing incorrect
automata from multitape expressions.
286

Akim Demaille's avatar
Akim Demaille committed
287
288
289
290
291
292
293
294
### Polynomials featuring the zero-label
Under some circumstances it was possible to have polynomials featuring
monomials whose label is the zero of the labelset (e.g., `\z` with
expressions as labels).  This is fixed.

### Portability issues
Newest compilers are now properly supported.

Akim Demaille's avatar
Akim Demaille committed
295
## Changes
Akim Demaille's avatar
Akim Demaille committed
296
### Divisions
Akim Demaille's avatar
Akim Demaille committed
297
298
299
The division of expressions and automata now compute the product of the
weights, not their quotient.

Akim Demaille's avatar
Akim Demaille committed
300
301
302
303
304
305
306
307
### Handling of the compose operator
The support of the compose operators in expansions was completely rewritten.
As a result, the derived-term automata are often much smaller, since many
useless states (non coaccessible) are no longer generated.

For instance the derived-term automaton of `(\e|a)* @ (aa|\e)*` has exactly
two states.  It used to have three additional useless states.

Akim Demaille's avatar
Akim Demaille committed
308
309
310
311
312
313
### Better diagnostics
Many error messages have been improved.

The Daut automaton format now treats `->` as a keyword, so `0->1 a` is now
properly read instead of producing a weird error message because Vcsn
thought your state was named `0->1`.
314

Akim Demaille's avatar
Akim Demaille committed
315
----------------------------------------------------------------------
316

317
# Vcsn 2.5 (2017-01-28)
Akim Demaille's avatar
Akim Demaille committed
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349

The Vcsners are proud to announce the release of Vcsn 2.5, aka the
k-lightest release!

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

Akim Demaille's avatar
Akim Demaille committed
350
351
352
## 2017-01-23
### Improved error messages
Parse errors were improved with caret-style reports for expressions and
353
automata in dot (Graphviz) and daut syntax.
Akim Demaille's avatar
Akim Demaille committed
354
355
356
357
358
359

    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
360
361
362
363
364
365
366
367
368
369
370
371
372

    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"]}')
Akim Demaille's avatar
Akim Demaille committed
373
374
375
376
377
378
379
    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

380

381
382
383
384
385
## 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.).

Sébastien Piat's avatar
Sébastien Piat committed
386
387
388
389
390
391
392
393
394
395
396
## 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.

Akim Demaille's avatar
Akim Demaille committed
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
## 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"));

Younes Khoudli's avatar
Younes Khoudli committed
426
427
428
429
## 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
Akim Demaille's avatar
Akim Demaille committed
430
of the automata, to tailor the display of expressions, etc.
Younes Khoudli's avatar
Younes Khoudli committed
431

Akim Demaille's avatar
Akim Demaille committed
432
433
For a start, it provides a simple means to get the configuration
information, including from Vcsn Tools.
Younes Khoudli's avatar
Younes Khoudli committed
434
435
436
437
438
439
440
441
442

    $ 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
Akim Demaille's avatar
Akim Demaille committed
443

Akim Demaille's avatar
Akim Demaille committed
444
445
446
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.

Akim Demaille's avatar
Akim Demaille committed
447
448
449
## 2016-12-20
### compare: new algorithm
Three-way comparison is now available in all the layers, as `compare`, for
450
451
452
automata, expressions, labels, polynomials and weights.  This is used in
Python to implement the comparisons (`<`, `<=`, `>`, `=>`, `==`, `!=`) of
expressions, and of automata (`<`, `<=`, `>`, `=>`).
Akim Demaille's avatar
Akim Demaille committed
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469

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

470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
## 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.
Akim Demaille's avatar
Akim Demaille committed
493

494

Akim Demaille's avatar
Akim Demaille committed
495
496
----------------------------------------------------------------------

Akim Demaille's avatar
Akim Demaille committed
497
# Vcsn 2.4 (2016-11-16)
Akim Demaille's avatar
Akim Demaille committed
498

Akim Demaille's avatar
Akim Demaille committed
499
The Vcsn team is happy to announce the release of Vcsn 2.4, code-named "the
500
quotient tools"!
Akim Demaille's avatar
Akim Demaille committed
501
502
503
504
505
506
507
508
509
510
511

Noteworthy changes include, besides a few bug fixes:

- an overhaul of the "Vcsn Tools" (previously known as TAF-Kit).  Because
  the tools are now automatically generated, they are much more extensive
  than previously: (almost) all of the dyn algorithms are now available from
  the shell.  It now also supports the 'daut' format for automata.

    $ vcsn thompson -Ee '[ab]*c' | vcsn proper | vcsn determinize | vcsn minimize | vcsn to-expression
    (a+b)*c

512
513
    $ vcsn random-expression -C 'lal(abc), z' '+, ., w., length=20, w="min=-2, max=10"'
    (a+<2>(ac)+<5>(acca))a
Akim Demaille's avatar
Akim Demaille committed
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564

- an new method to construct an automaton from an extended expression:
  `expression.inductive`.  This provides an alternative to
  `expression.derived_term`.  Currently provides a single flavor: generation
  of standard automata.

    In [2]: vcsn.B.expression('! [ab]*a[ab]*').inductive().expression()
    Out[2]: \e+bb*

    In [3]: vcsn.B.expression('! [ab]*a[ab]*').automaton().expression()
    Out[3]: b*

- full support for quotient operators on all entities: labels, expressions,
  automata, expansions, etc.

    In [2]: c = vcsn.context('lan, q')
       ...: c
    Out[2]: {...}? -> Q

    In [3]: label = vcsn.context('law, q').label
       ...: label('abc') / label('c')
    Out[3]: ab

    In [4]: exp = c.expression

    In [5]: exp('ab').ldivide(exp('ab*c'))
    Out[5]: ab{\}ab*c

    In [6]: e = exp('ab').ldivide(exp('ab*c'))
       ...: e
    Out[6]: ab{\}ab*c

    In [7]: e.automaton().expression()
    Out[7]: b*c

  Operators {\} (left quotient) and {/} (right quotient) are available in
  the rational expressions:

    In [8]: e = exp('ab {\} abc*')
       ...: e
    Out[8]: ab{\}abc*

    In [9]: e.expansion()
    Out[9]: \e.[b{\}bc*]

    In [10]: e.derived_term().expression()
    Out[10]: c*

    In [11]: e.inductive().expression()
    Out[11]: \e+cc*

Akim Demaille's avatar
Akim Demaille committed
565
- `automaton.evaluate` works properly on non-free automata, including
Akim Demaille's avatar
Akim Demaille committed
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
  multitape automata:

    In [2]: c = vcsn.context('lan(a-z), nmin')
            a = (c|c).levenshtein()
            a('foo|bar')
    Out[2]: 3

- input/output support for FAdo's format for transducers, and improved
  compatibility with OpenFST.

For more information, please, see the detailed news below.

People who worked on this release:

- Akim Demaille
- Clément Gillard
- Lucien Boillod
- Sarasvati Moutoucomarapoulé
- Sébastien Piat
- Younes Khoudli

People who have influenced this release:

- Alexandre Duret-Lutz
- Jacques Sakarovitch
- Luca Saiu
- Sylvain Lombardy

594
595
596
597
598
599
600
601
602
## 2016-11-04
### random_automaton now generates weights

`context.random_automaton` now takes an optional `weights` parameter,
allowing to set how the weights are generated. The syntax is the same
as the `param` string of `random_weights`.

    In [1]: import vcsn
            ctx = vcsn.context('lal_char(ab), z')
603
604
605
606
607
608
609
610
611
612
            a = ctx.random_automaton(3, weights='min=0, max=20')
            print(a.format('daut'))
    context = letterset<char_letters(ab)>, z
    $ -> 0
    0 -> $
    0 -> 2 <17>b
    1 -> 1 <13>b
    1 -> 2 <11>b
    2 -> 0 <18>a, <13>b
    2 -> 1 <12>a
613

Akim Demaille's avatar
Akim Demaille committed
614
615
616
617
618
## 2016-10-31
### eval is renamed evaluate
For consistency with the remainder of the API, we use the full,
unabbreviated, name: evaluate.

Younes Khoudli's avatar
Younes Khoudli committed
619
## 2016-10-18
Akim Demaille's avatar
Akim Demaille committed
620
621
### weight_zero and weight_one are now available in Python
These methods return the "zero" and "one" weights of a context.
Younes Khoudli's avatar
Younes Khoudli committed
622
623
624
625

    In [1]: import vcsn
            ctx = vcsn.context('lal_char, zmin')
    In [2]: ctx.weight_one()
Akim Demaille's avatar
Akim Demaille committed
626
    Out[2]: 0
Younes Khoudli's avatar
Younes Khoudli committed
627
628

    In [3]: ctx.weight_zero()
Akim Demaille's avatar
Akim Demaille committed
629
    Out[3]: ∞
Younes Khoudli's avatar
Younes Khoudli committed
630

631
632
633
634
635
636
637
638
639
640
## 2016-10-17
### Left and right divisions are now supported on labels
It is now possible to call left and right divisions on labels from Python,
using `//` and `/` operators (respectively).

    In [1]: import vcsn
            ctx = vcsn.context('law_char, b')
    In [2]: l = ctx.label('a')
            r = ctx.label('abc')
            l // r # == l.ldivide(r)
Akim Demaille's avatar
Akim Demaille committed
641
    Out[2]: bc
642
643
644
645

    In [3]: l = ctx.label('abc')
            r = ctx.label('bc')
            l / r # == l.rdivide(r)
Akim Demaille's avatar
Akim Demaille committed
646
    Out[3]: a
647

648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
## 2016-10-11
### TAF-Kit is replaced by Tools
The new command line interface is now automatically generated
from the algorithms in dyn, allowing it to support a lot more
functions than previously.

The supported algorithms are:

    accessible add ambiguous-word are-equivalent are-isomorphic cat
    cerny coaccessible codeterminize cominimize complement complete
    component compose concatenate condense conjugate conjunction
    constant-term context-of copy costandard cotrie de-bruijn
    delay-automaton derivation derived-term determinize difference
    divkbaseb eliminate-state eval expand expression-one expression-zero
    factor focus get-format has-bounded-lag has-lightening-cycle
    has-twins-property identities-of inductive infiltrate insplit
    is-accessible is-ambiguous is-coaccessible is-codeterministic
    is-complete is-costandard is-cycle-ambiguous is-deterministic
    is-empty is-eps-acyclic is-functional is-letterized is-normalized
    is-out-sorted is-partial-identity is-proper is-realtime is-standard
    is-synchronized is-synchronized-by is-synchronizing is-trim
    is-useless is-valid join ladybird ldivide less-than letterize
    levenshtein lgcd lift lightest lightest-automaton lweight
    make-context make-word-context minimize multiply normalize
    num-components num-tapes pair partial-identity prefix project proper
    push-weights quotkbaseb random-automaton
    random-automaton-deterministic random-expression random-weight
    rdivide realtime reduce rweight scc set-format shortest shuffle sort
    split standard star star-height star-normal-form strip subword
    suffix synchronize synchronizing-word thompson to-automaton
    to-expansion to-expression transpose transposition trie trim tuple
    type u universal weight-series zpc

681
To get more information about a particular algorithm, you can type
Akim Demaille's avatar
Akim Demaille committed
682
`vcsn COMMAND -h` or `--help`:
683
684
685
686
687
688
689
690
691
692
693

    $ vcsn eval --help
    usage: vcsn eval [OPTIONS...] [ARGS...]

    Available versions:
     eval: AUT:automaton P:polynomial -> weight
        Evaluate P on AUT.

     eval: AUT:automaton L:word -> weight
        Evaluate L on AUT.

Akim Demaille's avatar
Akim Demaille committed
694
    Try 'vcsn tools --help' for more information.
695
696
697
698
699
700
701
702
703
704
705
706
707
708

You can for example generate the Thompson automaton that accepts `ab*`:

    $ vcsn thompson 'ab*' -O daut
    $ -> 0
    0 -> 1 a
    1 -> 4 \e
    2 -> 3 b
    3 -> 2 \e
    3 -> 5 \e
    4 -> 2 \e
    4 -> 5 \e
    5 -> $

Akim Demaille's avatar
Akim Demaille committed
709
For more information, please see the Executables documentation page, and
710
711
`vcsn tools -h`.

712
## 2016-10-04
Akim Demaille's avatar
Akim Demaille committed
713
### FAdo: transducers and comments support
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
It is now possible to read and produce transducers in FAdo format.  Comments
are also supported in the parser.

    In [1]: a = vcsn.automaton(data='''
            @Transducer 0 2 * 0 # Final * Initial
            0 0 @epsilon 1
            0 0 0 0
            0 1 @epsilon 1
            0 1 1 0
            1 @epsilon 0 2
            1 @epsilon 1 2
            1 0 0 1
            1 1 1 1''')

    In [2]: print(a.format('fado'))
    @Transducer 0 2 * 0
    0 0 @epsilon 1
    0 0 0 0
    0 1 @epsilon 1
    0 1 1 0
    1 @epsilon 0 2
    1 @epsilon 1 2
    1 0 0 1
    1 1 1 1

## 2016-09-27
### daut native parser and producer
Daut is a simplified Dot syntax for automata.  This format was only available
in Python. It is now possible to read and produce it in C++.

    $ vcsn cat -A -I daut -O daut -f lal_char_q.daut
    context = letterset<char_letters(abc)>, q
    $ -> 0 <3>
    0 -> 1 <1/2>a, <1/3>b
    1 -> $ <2>

## 2016-09-21
Akim Demaille's avatar
Akim Demaille committed
751
### Improved compatibility with newer OpenFST
752
753
754
755
756
As OpenFST only supports a single initial state, pre is showed in case of
several ones, with spontaneous transitions to them.  Pre was represented by a
very large integer which was read as a negative one in newer version of
OpenFST, thus raising an error.  The state number immediately after the highest
state number is now used.
757

758
759
760
761
## 2016-09-19
### automaton.eval supports polynomials
It is now possible to evaluate polynomials of words on automata.

762
763
764
765
766
## 2016-09-12
### make_word_context is exposed in Python
It is now possible to call `context.word_context()` to get the context of the
words of any context.

767
## 2016-09-08
768
769
770
771
772
## automaton.eval supports non-free labelsets
It is now possible to evaluate words on automata with non-free labelsets.

For example, we can compute the edit distance between two words:

Akim Demaille's avatar
Akim Demaille committed
773
    In [2]: c = vcsn.context('lan(a-z), nmin')
774
775
            a = (c|c).levenshtein()
            a('foo|bar')
Akim Demaille's avatar
Akim Demaille committed
776
    Out[2]: 3
777

Akim Demaille's avatar
Akim Demaille committed
778
779
    In [3]: a('bar|baz')
    Out[3]: 1
780

Akim Demaille's avatar
Akim Demaille committed
781
782
    In [4]: a('qux|quuux')
    Out[4]: 2
783

784
## 2016-07-28
785
### expression: inductive
Akim Demaille's avatar
Akim Demaille committed
786
787
788
789
790
Implemented as a hidden feature in Vcsn 2.3, `expression.inductive` is a new
way of constructing automata from expressions, based on the algorithm given
as argument.  The only algorithm implemented yet is "standard" which uses
standard operations to construct a standard automaton. The difference with
`expression.standard` is that it handles extended expressions.
791
792
793
794

For example, we can compute the automaton equivalent of such expressions with
the inductive method whereas we cannot with the standard one:

Akim Demaille's avatar
Akim Demaille committed
795
796
    In [2]: vcsn.B.expression('! [ab]*a[ab]*').inductive().expression()
    Out[2]: \e+bb*
797

798
799
800
801
802
803
804
805
### expression.derived_term supports multitape expressions
Vcsn 2.3 already supports multitape expressions with the derived-term
algorithm, but it was restricted to the expansion-based computation.  The
derivative-based computation is now also supported.

This is only a proof of concept: the implementation is more complex and much
slower than the expansion-based approach.

806
807
808
## 2016-07-25
### expression.derivation works on multitape expressions
It is now possible to compute derivatives wrt labels such as `a|x`, `a|\e`
Akim Demaille's avatar
Akim Demaille committed
809
or `\e|x`.  It is however forbidden wrt `\e|\e`.
810

Akim Demaille's avatar
Akim Demaille committed
811
812
813
814
815
816
## 2016-07-23
### automaton.info: levels of detail
Instead of a Boolean argument `detailed`, `info` now features an integer
argument `details`, defaulting to 2.  A new level, 1, contains only basic
information (number of states and transitions).

Akim Demaille's avatar
Akim Demaille committed
817
## 2016-07-19
Akim Demaille's avatar
Akim Demaille committed
818
819
820
### expression: partial_identity
The `partial_identity` algorithm is now available on expressions too.

Akim Demaille's avatar
Akim Demaille committed
821
822
823
824
### tuple: applies to contexts
It is now possible from dyn and Python to tuple several contexts.  For
instance `vcsn.B | vcsn.Q` is `lat<lal, lal>, q`.

Akim Demaille's avatar
Akim Demaille committed
825

Akim Demaille's avatar
Akim Demaille committed
826
827
----------------------------------------------------------------------

Akim Demaille's avatar
Akim Demaille committed
828
# Vcsn 2.3 (2016-07-08)
Akim Demaille's avatar
Akim Demaille committed
829
830
831
832
833
834
835

About four hundred commits and five months after Vcsn 2.2, we are proud to
announce the release of Vcsn 2.3, code-named "the tuple release"!

As usual, many bugs were fixed (some quite old yet unnoticed so far!).
Noteworthy changes include:

Akim Demaille's avatar
Akim Demaille committed
836
837
- a particular effort was put on the documentation: there are thirty-five
  new documentation pages, and about forty others were improved.
Akim Demaille's avatar
Akim Demaille committed
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904

- full support for a "tuple" operator on all entities: expressions,
  polynomials, automata, etc.

    In [13]: aut = lambda e: vcsn.context('lan, q').expression(e).automaton()

    In [14]: a = aut('[ab]*') | aut('x')

    In [15]: a.shortest(6)
    Out[15]: \e|x + a|x + b|x + aa|x + ab|x + ba|x

  It is also available in the rational expressions themselves:

    In [16]: c = vcsn.context('lat<lan, lan>, q'); c
    Out[16]: {...}? x {...}? -> Q

    In [17]: e = c.expression('[ab]*|x'); e
    Out[17]: (a+b)*|x

    In [18]: e.shortest(6)
    Out[18]: \e|x + a|x + b|x + aa|x + ab|x + ba|x

  The derived-term algorithm supports this operator, and generates
  equivalent multitape automata.

- many error messages were improved, to help users understand their
  mistakes.  For instance, instead of

    In [2]: vcsn.Q.expression('a**').derivation('a')
    RuntimeError: q: star: invalid value: 1

  we now display:

    In [2]: vcsn.Q.expression('a**').derivation('a')
    RuntimeError: Q: value is not starrable: 1
      while computing derivative of: a**
                    with respect to: a

- in addition to `%automaton a`, which allows interactive edition of
  automata, the notebooks now feature two new interactive editors:
  `%context c` to edit/create context `c`, and `%expression e` for
  expressions (with an interactive display of the generated automata).

- one may now generate random rational expressions and control the
  operators and their probabilities.

- a lot of code improvement and consistency enforcement, both in C++ and in
  Python.

For more details, please, see the news below.

People who worked on this release:

- Akim Demaille
- Clément Gillard
- Lucien Boillod
- Raoul Billion
- Sébastien Piat
- Thibaud Michaud

People who have influenced this release:

- Alexandre Duret-Lutz
- Jacques Sakarovitch
- Luca Saiu
- Sylvain Lombardy

Akim Demaille's avatar
Akim Demaille committed
905
906
907
908
909
910
## 2016-06-28
### Command line executables
The shell tools (formerly known as TAF-Kit) such as `vcsn standard`, `vcsn
determinize`, etc. have finally been documented!  Several issues have been
fixed too.

Clément Gillard's avatar
Clément Gillard committed
911
912
913
914
915
916
917
## 2016-06-27
### expression widget
You can now use `%expression` in the notebook to interactively edit an
expression and its context while seeing the automaton it builds. You are also
able to chose the identities you want to use for the expression, and the automaton
generating algorithm used to render the automaton.

918
919
920
921
## 2016-06-20
### proper: more consistent signatures
The Python binding of `automaton.proper` was different from the static and
dyn:: versions for no sound reason: instead of a `direction` argument taking
922
`backward` or `forward`, it had a `backward` argument taking an Boolean,
923
924
925
926
927
and the `prune` and `direction` (well, `backward`) arguments were swapped.

The signature in Python is now consistent:
`aut.proper(direction="backward", prune=False, algo="auto", lazy=False)`.

928
## 2016-06-16
929
930
### renamings
The following operations have been renamed, in all APIs (vcsn::, dyn::,
931
932
Python, and TAF-Kit), and on all applicable types (automaton, expansion,
expression, polynomial, weight).
933
934

    infiltration -> infiltrate
935
    ldiv         -> ldivide
936
    left_mult    -> lweight
937
    rdiv         -> rdivide
938
    right_mult   -> rweight
939
    sum          -> add
940

941
## 2016-06-07
942
943
### random_automaton: new name for `random`
Random generation of automata is now named `random_automaton`.
944

945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
## 2016-05-27
### polynomials: more basic operations
Polynomials now support (in the three layers) the addition, multiplication,
exterior products, and conjunction.

    In [4]: p = vcsn.context('law, q').polynomial

    In [5]: p0 = p('<2>a + <3>b + <4>c'); p1 = p('<5>a + <6>b + <7>d')

    In [6]: p0 + p1
    Out[6]: <7>a + <9>b + <4>c + <7>d

    In [7]: p0 * p1
    Out[7]: <10>aa + <12>ab + <14>ad + <15>ba + <18>bb + <21>bd + <20>ca + <24>cb + <28>cd

    In [8]: p0 * 2
    Out[8]: <4>a + <6>b + <8>c

    In [9]: 2 * p0
    Out[9]: <4>a + <6>b + <8>c

    In [10]: p0 & p1
    Out[10]: <10>a + <18>b

969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
## 2016-05-25
### tuple: applies to more types
The Cartesian product, dubbed "tuple" in Vcsn, was already available on
expansions and expressions in the three layers (static, dyn, Python as `|`).
It is now also available on automata and on polynomials.

    In [2]: exp = vcsn.context('lan, q').expression

    In [3]: a = exp('(<2>a)*').automaton()
    In [4]: b = exp('x+y').automaton()

    In [5]: (a|b).shortest(8)
    Out[5]: \e|x + \e|y + <2>a|x + <2>a|y + <4>aa|x + <4>aa|y + <8>aaa|x + <8>aaa|y

    In [6]: a.shortest(4) | b.shortest(2)
    Out[6]: \e|x + \e|y + <2>a|x + <2>a|y + <4>aa|x + <4>aa|y + <8>aaa|x + <8>aaa|y

Clément Gillard's avatar
Clément Gillard committed
986
## 2016-05-20
Akim Demaille's avatar
Akim Demaille committed
987
### quotkbaseb: new algorithm
Clément Gillard's avatar
Clément Gillard committed
988
989
990
991
992
993
994
995
996
997
998
999
From a context, a divisor k, and a base b, gives a transducer that,
when given a number in b divisible by k, outputs the quotient of the division
of that number by k in b.

    In [2]: c = vcsn.context('lat<lal_char(0-9), lal_char(0-9)>, b')

    In [3]: c.quotkbaseb(3, 2).shortest(10)
    Out[3]: \e|\e + 0|0 + 00|00 + 11|01 + 000|000 + 011|001 + 110|010 + 0000|0000 + 0011|0001 + 0110|0010

    In [4]: c.quotkbaseb(7, 10).shortest(10)
    Out[4]: \e|\e + 0|0 + 7|1 + 00|00 + 07|01 + 14|02 + 21|03 + 28|04 + 35|05 + 42|06

1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
## 2016-05-02
### expansions: support for &
In addition to automata, expressions and polynomials, the conjunction can
now be performed on expansions.

## 2016-04-30
### sum: optimized version for deterministic automata
The sum of deterministic Boolean automata is now based on a synchronized
product-like approach.

### dyn: vast overhaul and factoring
The implementation of dyn:: values was revised and factored.  No visible
change.

## 2016-04-14
### random_expression
One may now generate random expressions.

1018
    In [2]: rand = vcsn.context('lal(abc), b').random_expression
1019

1020
    In [3]: rand('+,.', length=10)
1021
1022
    Out[3]: c(b+c+ca)c

1023
    In [4]: rand('+,.', length=10)
1024
1025
    Out[4]: c+abcac

1026
    In [5]: rand('+=1, .=1, *=.2', length=10)
1027
1028
    Out[5]: (b(a+b+c))*

1029
    In [6]: rand('+=1, .=1, *=.2', length=10)
1030
1031
    Out[6]: bb*ca

1032
    In [7]: rand('+=1, .=1, *=.2, &=1', length=10)
1033
1034
    Out[7]: c

1035
    In [8]: rand('+=1, .=1, *=.2, &=1', length=10)
1036
1037
    Out[8]: a*cb*

1038
    In [9]: rand('+=1, .=1, *=.2, &=1', length=10)
1039
    Out[9]: a((a+a*)&b*)*
1040
1041
1042
1043
1044
1045

## 2016-03-29
### project: support for expressions and expansions
One may now project (multitape) automata, contexts, expansions, expressions,
labels and polynomials.

1046
1047
## 2016-03-15
### expression: a dot output
Akim Demaille's avatar
Akim Demaille committed
1048
Expressions now feature a `"dot"` format to display graphically the structure
1049
of the expression.  There are actually two flavors: `"dot,logical"` (the
Akim Demaille's avatar
Akim Demaille committed
1050
default) which shows the semantic tree, and `"dot,physical"` which shows
1051
1052
1053
1054
1055
the DAG that is used to implement the expression (i.e., nodes used multiple
times are displayed only once).

Under IPython, experiment `exp.SVG()` (logical) and `exp.SVG(True)` (physical).

1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
### Python: __format__
The Python objects now support the `format` protocol.  For instance:

    In [2]: c = vcsn.context('lal(abc), q')

    In [3]: for i in range(4):
                e = c.expression('[ab]*a[ab]{{{i}}}'.format(i=i))
                print('{i:3d} | {e:t:20} | {e:u:20} | {n:3d}'
                      .format(i=i, e=e,
                              n=e.automaton().determinize().state_number()))
      0 | (a+b)*a              | (a+b)*a              |   2
      1 | (a+b)*a(a+b)         | (a+b)*a(a+b)         |   4
      2 | (a+b)*a(a+b){2}      | (a+b)*a(a+b)²        |   8
      3 | (a+b)*a(a+b){3}      | (a+b)*a(a+b)³        |  16

Akim Demaille's avatar
Akim Demaille committed
1071
## 2016-03-08
1072
### ldiv, rdiv: compute quotient between automata
1073
1074
`automaton.ldiv` and `automaton.rdiv` compute the left and right quotients of
two automata.
1075
1076
1077
1078
1079
1080
1081
1082

    In [1]: import vcsn
            ctx = vcsn.context('lal_char, b')
            aut = lambda e: ctx.expression(e).automaton()

    In [2]: aut('ab').ldiv(aut('abcd')).expression()
    Out[2]: cd

1083
1084
1085
    In [3]: (aut('abcd') / (aut('cd')).expression()
    Out[3]: ab

Akim Demaille's avatar
Akim Demaille committed
1086

Akim Demaille's avatar
Akim Demaille committed
1087
----------------------------------------------------------------------
Akim Demaille's avatar
Akim Demaille committed
1088

Akim Demaille's avatar
Akim Demaille committed
1089
# Vcsn 2.2 (2016-02-19)
Akim Demaille's avatar
Akim Demaille committed
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137

We are very happy to announce the release of Vcsn 2.2!  This version,
code-named "the lazy release", concludes the work from Antoine and Valentin,
who left EPITA for their final internship.

In addition to the usual load of improvements (more doc and less bugs), this
version features some noteworthy changes:

- several algorithms now offer a lazy variant: compose, conjunction,
  derived_term, determinize, insplit, and proper.  Instead of completing the
  construction on invocation, the result is built incrementally, on demand,
  e.g., when requested by an evaluation.

  This is especially useful for large computations a fraction of which is
  actually needed (e.g., composition of two large automata and then with a
  small one), or for computations that would not terminate (e.g.,
  determinization of some weighted automata).

- the functions `automaton.lightest` and `automaton.lightest_automaton`
  explore the computations (i.e., paths of accepted words) with the smallest
  weights (dubbed "shortest paths" for tropical-min semirings).  They
  feature several implementations controlled via the `algo` argument.

- rational expressions now support UTF-8 operators in input and output.
  They also learned a few tricks to be better looking (e.g., `aaa` => `a³`).

- several new algorithms or improvements or generalizations of existing ones.

- a number of performance improvements.

Please, see the details below.

People who worked on this release:

- Akim Demaille
- Antoine Pietri
- Lucien Boillod
- Nicolas Barray
- Raoul Billion
- Sébastien Piat
- Thibaud Michaud
- Valentin Tolmer

People who have influenced this release:

- Alexandre Duret-Lutz
- Jacques Sakarovitch
- Luca Saiu
Akim Demaille's avatar
Akim Demaille committed
1138
- Sylvain Lombardy
Akim Demaille's avatar
Akim Demaille committed
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148

## 2016-02-13
### operations on automata: deterministic versions
In addition to the `"general"`, `"standard"` and `"auto"` variants,
multiply, sum and star now support a `"deterministic"` variant, which
guarantees a deterministic result.

Beware that with infinite semirings, some (deterministic) operations might
not terminate.

1149
## 2016-02-05
Akim Demaille's avatar
Akim Demaille committed
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
### conjugate: new algorithm
The `automaton.conjugate` function builds an automaton whose language is the
set of conjugates (i.e., "rotations", or "circular permutations") of the
words accepted by the input automaton.

    In [3]: vcsn.context('lan_char, b')         \
                .expression('(ab)*')            \
                .automaton()                    \
                .conjugate()                    \
                .expression()
    Out[3]: (ab)*+(ab)*{2}+(ba)*ba(ba)*

1162
1163
1164
### demangle: add a gdb pretty-printer for Vcsn types
`vcsn gdb` runs gdb with a pretty-printer, which will automatically Vcsn's
`demangle()` function when a variable with a vcsn type is printed.  Symbols
1165
are then *much* easier to read.
1166

1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
### insplit: support for on-the-fly construction
The implementation of `insplit` now supports a `lazy` argument. This is
especially useful when composing a small transducer with a big one, to avoid
computing the insplit of the right transducer for many states, that are not
going to be useful.

It is used in the composition algorithm for this very reason.

### compose: support for on-the-fly construction
The implementation of `compose` now supports a `lazy` argument. This is
especially useful when composing two big transducers, and then compose with
several small ones. The result of the first composition, although huge, will
never be completely computed, but the required states are computed and cached.

## 2016-01-28
Akim Demaille's avatar
Akim Demaille committed
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
### determinize: support for on-the-fly construction
The implementation of `determinize` now supports a `lazy` argument.  This is
especially useful when working on automata that do not admit a (finite)
deterministic automaton.

For instance:

    In [2]: a = vcsn.Z.expression('a*+(<2>a)*').automaton().determinize(lazy=True)

    In [3]: print(a.as_boxart())
        ╭───╮
    ──> │ 0 │
        ╰───╯

    In [4]: a('')
    Out[4]: 2

    In [5]: print(a.as_boxart())
        ╭───╮  a   ╭─────────╮
    ──> │ 0 │ ───> │ 1, ⟨2⟩2 │
        ╰───╯      ╰─────────╯

          │ ⟨2⟩


    In [6]: a('aa')
    Out[6]: 5

    In [7]: print(a.as_boxart())
        ╭───╮  a   ╭─────────╮  a   ╭─────────╮  a   ╭─────────╮
    ──> │ 0 │ ───> │ 1, ⟨2⟩2 │ ───> │ 1, ⟨4⟩2 │ ───> │ 1, ⟨8⟩2 │
        ╰───╯      ╰─────────╯      ╰─────────╯      ╰─────────╯
          │            │                │
          │ ⟨2⟩        │ ⟨3⟩            │ ⟨5⟩
          ∨            ∨                ∨

Akim Demaille's avatar
Akim Demaille committed
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
## 2016-01-14
### lightest: algorithms for "shorter paths"
The `automaton.lightest` looks for words (possibly several) whose evaluation
is the smallest one in the automaton.  In the case of ℕmin and other
tropical semiring, this is often referred to as "shortest paths", but it
applies to other semirings as well.  It features the same interface as
`automaton.shortest` (which looks for shortest accepted words), but offers
several variants, such as `"dijkstra"`, `"bellman-ford"`, `"auto"`...

The `automaton.lightest_automaton` algorithm returns a slice of the
automaton corresponding to the evaluation with the small weight.  It also
offers several variants.

Akim Demaille's avatar
Akim Demaille committed
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
## 2016-01-09
### derived-term: support for on-the-fly construction
The implementation of `derived_term` now supports a `lazy` argument.  This
is especially useful when working on "infinite derived-term automata" (which
happens when requesting a deterministic automaton, or when using the
complement operator).

For instance:

    In [2]: a = vcsn.Z.expression('a*+(<2>a)*').derived_term(deterministic=True, lazy=True)

    In [3]: print(a.as_boxart())
Akim Demaille's avatar
Akim Demaille committed
1243
1244
1245
         ╭────────────╮
     ──> │ a*+(⟨2⟩a)* │
         ╰────────────╯
Akim Demaille's avatar
Akim Demaille committed
1246
1247
1248
1249
1250

    In [4]: a('')
    Out[4]: 2

    In [5]: print(a.as_boxart())
Akim Demaille's avatar
Akim Demaille committed
1251
1252
1253
1254
1255
1256
        ╭────────────╮  a   ╭───────────────╮
    ──> │ a*+(⟨2⟩a)* │ ───> │ a*+⟨2⟩(⟨2⟩a)* │
        ╰────────────╯      ╰───────────────╯

          │ ⟨2⟩

Akim Demaille's avatar
Akim Demaille committed
1257
1258
1259
1260
1261

    In [6]: a('aa')
    Out[6]: 5

    In [7]: print(a.as_boxart())
Akim Demaille's avatar
Akim Demaille committed
1262
1263
1264
1265
1266
1267
        ╭────────────╮  a   ╭───────────────╮  a   ╭───────────────╮  a   ╭───────────────╮
    ──> │ a*+(⟨2⟩a)* │ ───> │ a*+⟨2⟩(⟨2⟩a)* │ ───> │ a*+⟨4⟩(⟨2⟩a)* │ ───> │ a*+⟨8⟩(⟨2⟩a)* │
        ╰────────────╯      ╰───────────────╯      ╰───────────────╯      ╰───────────────╯
          │                      │                      │
          │ ⟨2⟩                  │ ⟨3⟩                  │ ⟨5⟩
          ∨                      ∨                      ∨
Akim Demaille's avatar
Akim Demaille committed
1268

1269
1270
1271
1272
## 2015-12-31
### project is available on more structures
One may now project not only multitape automata, but also contexts, labels
and polynomials.
1273

1274
## 2015-12-23
Akim Demaille's avatar
Akim Demaille committed
1275
### has-lightening-cycle: new name for `has-negative-cycle`
Akim Demaille's avatar
Akim Demaille committed
1276
In static, dyn:: and Python, `has-negative-cycle` is renamed
1277
`has-lightening-cycle`. It makes more sense as we consider `(<1/2>a)*` to be a
1278
1279
lightening cycle.

Akim Demaille's avatar
Akim Demaille committed
1280
1281
1282
1283
## 2015-12-21
### Operators on expressions and expansions
The `dyn::complement` function is now available on expansions, in addition
to expressions and automata.  It is bound to the prefix `~` operator in
Akim Demaille's avatar
Akim Demaille committed
1284
Python.  The `dyn::tuple` function is available for expressions and
Akim Demaille's avatar
Akim Demaille committed
1285
1286
expansions.  It is bound to `|` in Python.

Akim Demaille's avatar
Akim Demaille committed
1287
## 2015-12-10
Akim Demaille's avatar
Akim Demaille committed
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
### Exponents in expressions
In addition to "ASCII exponents" in input (e.g., `(ab){4}`), we now support
them in output, possibly in UTF-8:

    In [7]: vcsn.B.expression('aa{2}a²')
    Out[7]: a{5}
    In [8]: print(vcsn.B.expression('aa{2}a²').format('utf8'))
    a⁵

This is especially nice in derived-term automata.

Akim Demaille's avatar
Akim Demaille committed
1299
### Tag based dispatch in vcsn::
Akim Demaille's avatar
Akim Demaille committed
1300
1301
1302
1303
1304
The treatments for which several algorithms exist (e.g., minimize/cominimize
---hopcropft, moore, weighted, signature, brzozowski, auto---,
determinize/codeterminize ---boolean, weighted, auto---, sum/multiply/star
---standard, general, auto---, etc.) now offer a cleaner tag-based interface
in vcsn::, the static library.  For instance, instead of:
Akim Demaille's avatar
Akim Demaille committed
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356

    auto m = minimize_moore(a);

write:

    auto m = minimize(a, moore_tag{});

### dot format
The HTML/XML style strings are now properly supported.

### oneset and proper
The oneset labelset has a single label: one.  It is used to denote automata
with spontaneous transitions only.  Applying proper on such automata
resulted in an ill-formed automaton (with a single subliminal transition
from pre to post).  This is now fixed.

### Flex 2.6
We are now compatible with the new Flex, which made backward incompatible
changes in its API.  Previous versions are supported too.

### Text format
When displaying value sets, the `text` format was improved, and the new
format `utf8` improves on top of it.  An new format name `sname`, replaces
previous uses of `text`:

    In [2]: c = vcsn.context('lal_char(abc), expressionset<law_char(xyz), q>')

    In [3]: c.format('sname')
    Out[3]: 'letterset<char_letters(abc)>, expressionset<wordset<char_letters(xyz)>, q>'

    In [4]: c.format('text')
    Out[4]: '{abc} -> RatE[{xyz}* -> Q]'

    In [5]: c.format('utf8')
    Out[5]: '{abc} → RatE[{xyz}* → ℚ]'

When displaying values, the new format `utf8` improves the result.

    In [6]: e = c.expression('!(<x>a)*')

    In [7]: e.format('text')
    Out[8]: '(<x>a)*{c}'

    In [9]: e.format('utf8')
    Out[9]: '(⟨x⟩a)*ᶜ'

    In [10]: e.expansion().format('text')
    Out[10]: 'a.[(<x>a)*{c}] + b.[\\z{c}] + c.[\\z{c}]'

    In [11]: e.expansion().format('utf8')
    Out[11]: 'a⊙[(⟨x⟩a)*ᶜ] ⊕ b⊙[∅ᶜ] ⊕ c⊙[∅ᶜ]'

1357
1358
## 2015-12-08
### polynomial: conjunction
Akim Demaille's avatar
Akim Demaille committed
1359
1360
Conjunction of polynomials is now available in dyn. For polynomials of
expressionsets, compute the conjunction of the expressions. Otherwise, keep
1361
the common labels and multiply their weights.
Akim Demaille's avatar
Akim Demaille committed
1362
1363
1364
1365
1366
1367

## 2015-12-05
### Syntactic sugar in expressions
One may now use UTF-8 when entering expressions.  The negation may also be
denoted by a prefix `!`, which binds weakly (less than concatenation).

1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
    +--------+----------------+
    | Sugar  | Plain ASCII    |
    +========+================+
    | `∅`    | `\z`           |
    +--------+----------------+
    | `ε`    | `\e`           |
    +--------+----------------+
    | `⟨2⟩a` | `<2>a`         |
    +--------+----------------+
    | `a∗`   | `a*`           |
    +--------+----------------+
    | `!a`   | `a{c}`         |
    | `¬a`   |                |
    | `aᶜ`   |                |
    +--------+----------------+
    | `aᵗ`   | `a{T}`         |
    +--------+----------------+
1385

1386
1387
1388
1389
1390
1391
## 2015-12-04
### weight_series: fix general case
This algorithm can now be applied to any automaton. In case of ℕmin weightset
the implementation does not change (shortest path). Otherwise, the result is
computed by applying proper on the `labels_are_one` version of the automaton.

1392
1393
1394
1395
1396
1397
1398
### New trivial identities
Two new trivial identities have been added (at the "trivial" level):
neutrality of the universal language for conjunction (\z{c} & E => E, E &
\z{c} => E), and involutivity of complement on 𝔹 and 𝔽₂ (E{c}{c} => E).
It is not applied in the other case, since in ℤ (<2>a)*{c}{c} is actually
a*, not (<2>a)*.

1399
1400
1401
1402
1403
## 2015-12-02
### left-mult and right-mult
The scalar product now also accept an argument to select the exact
algorithm: "standard", "general", "auto".  See 2015-11-13 for more details.

1404
1405
1406
1407
1408
## 2015-12-02
### to-automaton: trim automata
Now `to_automaton` (or `expression.automaton` under Python) always produces
a trim automaton.

Akim Demaille's avatar
Akim Demaille committed
1409
1410
1411
1412
1413
1414
1415
## 2015-11-29
### Improved display of letter classes
So far disjunction of letters were displayed as classes only if all
the letters had the same weight.  So `<1>a + <2>[^a]` in an automaton
resulted in an explicit list of letters.  This is especially
inappropriate for Levenshtein automata.  We now display `<1>a + <2>[^a]`.

1416
1417
1418
1419
1420
1421
## 2015-11-20
### weight_series: new algorithm
Compute the sum of all the weights of the accepted words (the sum of the
image of the behavior of the automaton). This algorithm can be applied to any
Nmin automaton, but requires acyclic automata for other weightsets.

Akim Demaille's avatar
Akim Demaille committed
1422
1423
1424
1425
1426
1427
1428
1429
## 2015-11-19
### trie and cotrie are enhanced
Both context.trie and context.cotrie accept `data`, `format` and `filename`
arguments.  In addition to `filename`, one can now pass directly a list of
words as a `data` string.  Use `format` to specify whether the lines are
 monomials or plain words --- for instance whether `<2>a` is the word `a`
with weight 2, or a four-letter word.

1430
1431
1432
1433
1434
1435
### Minimize: new algorithm: hopcroft
There is now a new implementation of the minimization, based on the
algorithm of Hopcroft.  It can only be used on Boolean automata with a free
labelset.  On many examples, this algorithm shows better performances than
"signature" but is still less efficient than "moore".

Akim Demaille's avatar
Akim Demaille committed
1436
## 2015-11-13
1437
### Automata: operations now work on all sorts of automata
Akim Demaille's avatar
Akim Demaille committed
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
Usual operations (`sum`, `multiply` --which includes the case for repeated
multiplication--, `star`) used to apply only to standard automata.  In
addition to `sum` (for standard automata), there was `union`, which applied
to any automata, but nothing for multiplication and star.

Now `sum`, `star` and `multiply` accept an `algo` argument:

"standard"
:   requires standard input automata, builds a standard automaton

"general"
:   applies to any kind of automaton, does not guarantee a standard
    automaton.  In the static API, might require a nullable labelset,
    in the dyn:: API and Python, might turn the labelset into a nullable
    one.

"auto" (default)
:   same as `"standard"` if input automata are standard, otherwise
    same as `"general"`.

In Python, the operators `+`, `*` and `**` use the `"auto"` strategy.

The `union` algorithms are removed, and in Python `|` no longer denotes it.
The left and right multiplication by a scalar were already implemented to
adapt standard or non standard automata.

Akim Demaille's avatar
Akim Demaille committed
1464
1465
1466
1467
1468
## 2015-11-05
### Expansions: more operations
Usual operations (addition, multiplication, multiplication by a scalar) are
now available on expansions.

Akim Demaille's avatar
Akim Demaille committed
1469
## 2015-10-15
Akim Demaille's avatar
Akim Demaille committed
1470
1471
1472
1473
### has_negative_cycles: new algorithm
Use automaton.has_negative_cycle to check whether an automaton has cycles
with negative weights.

Akim Demaille's avatar
Akim Demaille committed
1474
1475
1476
1477
1478
1479
1480
1481
1482
### Minor bug fixes and improvements
- Spaces are now ignored in context names (e.g., ` lal < char (ab) >, b `).

- Expressions that have a single tape but several were expected are now
  properly rejected.

- Tuples now display parentheses only when needed.  For instance with
  weights in ℤ ⨉ ℤ, instead of `<(1, 2)>a`, we display `<1, 2>a`.

Akim Demaille's avatar
Akim Demaille committed
1483

Akim Demaille's avatar
Akim Demaille committed
1484
----------------------------------------------------------------------
Akim Demaille's avatar
Akim Demaille committed
1485

Akim Demaille's avatar
Akim Demaille committed
1486
# Vcsn 2.1 (2015-10-11)
Akim Demaille's avatar
Akim Demaille committed
1487
1488

About 10,000 hours (on the calendar, not of work!) after its first public
Akim Demaille's avatar
Akim Demaille committed
1489
release, the Vcsn team is very happy to announce the release of Vcsn 2.1!
Akim Demaille's avatar
Akim Demaille committed
1490
1491
1492
1493
1494
1495

It is quite hard to cherry-pick a few new features that have been added in
Vcsn 2.1, as shown by the 4k+ lines of messages below since 2.0.  However,
here are a few headlines:

- Many pages of documentation and examples have been written (see
Akim Demaille's avatar
Akim Demaille committed
1496
  http://vcsn.lrde.epita.fr/dload/2.1/notebooks).
Akim Demaille's avatar
Akim Demaille committed
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509

- Now http://vcsn-sandbox.lrde.epita.fr/ provides a live demo.

- Transducers are much better supported, with improved syntax and several
  algorithms (e.g., letterize, synchronize, partial_identity, is_functional,
  etc.)

- Expressions now offer several sets of identities specifying how they
  should be normalized.  More generally, input/output of expressions have
  been improved to match most users' expectations.  New operators are
  accepted: `&` for conjunction, `:` for shuffle, `&:` for infiltration,
  `{c}` (postfix) for complement, and `<+` for deterministic choice.

Akim Demaille's avatar
Akim Demaille committed
1510
1511
- When entering an automaton (e.g., with `%%automaton` in IPython) user
  state names are preserved.
Akim Demaille's avatar
Akim Demaille committed
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524

- Of course, many bugs were fixed, many algorithms were sped up, and
  internal details have been cleaned up.

- As Easter eggs, many features have also been added, but not advertised,
  until we are sure of how we want them to look like.

People who worked on this release:

- Akim Demaille
- Antoine Pietri
- Canh Luu
- Clément Démoulins
1525
- Lucien Boillod
Akim Demaille's avatar
Akim Demaille committed
1526
1527
1528
1529
1530
1531
- Nicolas Barray
- Sébastien Piat
- Sylvain Lombardy
- Valentin Tolmer
- Yann Bourgeois--Copigny

Akim Demaille's avatar
Akim Demaille committed
1532
People who have influenced this release:
Akim Demaille's avatar
Akim Demaille committed
1533
1534
1535
1536
1537

- Alexandre Duret-Lutz
- Jacques Sakarovitch
- Luca Saiu

1538

Akim Demaille's avatar
Akim Demaille committed
1539
1540
1541
1542
1543
### Vcsn 2's repository has moved
To update your existing repository, run a command similar to:

    $ git remote set-url origin git@gitlab.lrde.epita.fr:vcsn/vcsn

1544
1545
## 2015-09-30
### shortest: applies to any automaton
Akim Demaille's avatar
Akim Demaille committed
1546
1547
The restriction to free-labelsets is lifted: shortest applies to automata
labeled with words, to transducers, etc.
1548

1549
1550
1551
1552
## 2015-09-28
### project: new algorithm
Select a single tape from a multitape automaton (transducer).

Akim Demaille's avatar
Akim Demaille committed
1553
1554
1555
1556
1557
## 2015-09-23
### expressions: spaces are now ignored
In an attempt to look like regexps, spaces were considered so far as
characters.

1558
1559
1560
1561
1562
## 2015-09-17
### derived-term: deterministic automata
One can now require the construction of a deterministic automaton; there are
two new algorithms: `expansion,deterministic` and `derivation,deterministic`.

1563
1564
1565
## 2015-09-15
### Named automata
It is (finally) possible to keep user state names thanks to
Akim Demaille's avatar
Akim Demaille committed
1566
1567
1568
1569
`name_automaton<Aut>`.  Now `dyn::read_automaton` and (in Python)
`vcsn.automaton` accept an additional `strip` argument (defaulting to true):
if set, the user names will be stripped once the automaton is loaded.  This
applies to all the supported formats: Daut, Dot, Efsm, and FAdo.
1570

Akim Demaille's avatar
Akim Demaille committed
1571
1572
However using `%%automaton` names are kept by default.  Pass `-s`/`--strip`
to strip it.
1573

1574
1575
1576
1577
1578
## 2015-09-07
### Build fixes
Fixed (again) nasty shared-library issues at runtime on Ubuntu due to their
use of `-Wl,--as-needed`.  This affected Python only.

1579
1580
1581
1582
1583
1584
## 2015-08-31
### expression.info: more information
Now `atom` (the number of occurrences of letters) is also reported as
`width`, and the `depth` (also known as the `height`: the height of the
tree) is now included.

1585
1586
1587
1588
1589
## 2015-08-26
### vcsn.automaton can guess the format
The vcsn.automaton function now accepts "auto" as format, which means "try
to guess from the content".

1590
1591
## 2015-08-25
### levenshtein: new algorithm
Akim Demaille's avatar
Akim Demaille committed
1592
1593
1594
1595
1596
The `levenshtein` algorithm allows to build a transducer encoding the
Levenshtein distance between two alphabets. This transducer can then be
composed with two languages to obtain the edit-distance algorithm,
containing much information on the distance of the languages and their
words.
1597

Akim Demaille's avatar
Akim Demaille committed
1598
### partial_identity: new algorithm
Valentin Tolmer's avatar
Valentin Tolmer committed
1599
1600
1601
1602
The partial identity turns an automaton into a transducer realizing a partial
identity. I.e., for each accepted input, the output will be the same as the
input (plus the origin weight from the input automaton).

1603
1604
1605
1606
1607
## 2015-08-18
### to_automaton: more algorithms
One can chose between both implementation of derived_term (stripped), using
"derivation" or "expansion".

1608
1609
1610
1611
1612
## 2015-08-14
### to_expression: more heuristics
There are three new heuristics:

"delgado"
Akim Demaille's avatar
Akim Demaille committed
1613
1614
:   select a state whose removal would contribute a small
    expression (number of symbols, including `+`, etc.).
1615
1616

"delgado_label"
Akim Demaille's avatar
Akim Demaille committed
1617
1618
:   likewise, but count only the number of labels in the
    expression.
1619
1620
1621
1622
1623
1624

"best"
:   run all the heuristics, and return the shortest result.

The default algorithm remains "auto", which now denotes "best".

1625
1626
1627
1628
## 2015-08-03
### to_automaton: conversion from expression to automaton
Vcsn offers several means to build an automaton from an expression:
thompson, zpc, standard and derived-term.  The latter even builds a
Akim Demaille's avatar
Akim Demaille committed
1629
decorated automaton, which, often, is not desired.
1630

Akim Demaille's avatar
Akim Demaille committed
1631
1632
In C++ `dyn::to_automaton` and in Python `expression.automaton()` allow to
build a simple automaton from an expression.  It accepts an optional string
Akim Demaille's avatar
Akim Demaille committed
1633
1634
1635
1636
1637
argument to select the conversion algorithm.  It defaults to "auto", which
currently means the stripped derived-automaton, but eventually, it will pick
either "standard" for basic expressions (as it's the fastest algorithm), or
"derived-term" for extended expressions (as "standard" does not support
these additional operators).
1638

1639
1640
## 2015-06-18
### I/O in EFSM format are safer
Akim Demaille's avatar
Akim Demaille committed
1641
We now correctly ensure the correspondence between our weightsets and
Akim Demaille's avatar
Akim Demaille committed
1642
1643
OpenFST's arc-type, and input and output.

Akim Demaille's avatar
Akim Demaille committed
1644
1645
1646
1647
As a consequence, we no longer support exchange of "traditional numerical"
weightsets (such as "Z", "R", etc.), since, as far as we know, they don't
feature a vis-à-vis in OpenFST.  It used to be accepted, but was
meaningless.
Akim Demaille's avatar
Akim Demaille committed
1648
1649
1650

Boolean weights are mapped to "standard", OpenFST's tropical semiring.

Akim Demaille's avatar
Akim Demaille committed
1651
1652
1653
1654
When reading EFSM files, we still try to use the smallest corresponding
weightset.  For instance, if the arc type is "standard" and and the weights
are integral we use "zmin", otherwise, we use "rmin".  Errors on reading the
weight of final states have also been fixed.
Akim Demaille's avatar
Akim Demaille committed
1655

1656
1657
1658
1659
1660
## 2015-06-16
### automaton.expression, automaton.lift
They now accept an optional argument to specify the desired identities
for the expressions.

Akim Demaille's avatar
Akim Demaille committed
1661
1662
1663
1664
## 2015-06-15
### power, chain have been renamed
Before, "chain" denoted the repeated concatenation for automata and
expressions, and "power" meant repeated conjunction for automata and
Akim Demaille's avatar
Akim Demaille committed
1665
1666
expressions.  However, while `aut ** 2` meant `aut & aut` (conjunction),
`exp ** 2` meant `exp * exp` (concatenation).
Akim Demaille's avatar
Akim Demaille committed
1667

Akim Demaille's avatar
Akim Demaille committed
1668
1669
Clearly, from the Python point of view, `**` is repeated `*`, which is what
most people would understand as "power".
Akim Demaille's avatar
Akim Demaille committed
1670

Akim Demaille's avatar
Akim Demaille committed
1671
1672
So, to enforce consistency, and to avoid bad surprises, these functions were
renamed.
Akim Demaille's avatar
Akim Demaille committed
1673

1674
    +----------+---------------------+------------------------------------+
1675
    | Python   | dyn::               | Comment                            |
1676
    +==========+=====================+====================================+
1677
1678
1679
    | `a * b`  | `multiply(a, b)`    | Multiplication for automata and    |
    |          |                     | expressions (concatenation),       |
    |          |                     | polynomials, weights, labels etc.  |
1680
    +----------+---------------------+------------------------------------+
1681
    | `a ** n` | `multiply(a, n)`    | Repeated multiplication.           |
1682
    +----------+---------------------+------------------------------------+
1683
1684
    | `a & b`  | `conjunction(a, b)` | Conjunction for automata and       |
    |          |                     | expressions.                       |
1685
    +----------+---------------------+------------------------------------+
1686
    | `a & n`  | `conjunction(a, n)` | Repeated conjunction.              |
1687
    +----------+---------------------+------------------------------------+
Akim Demaille's avatar
Akim Demaille committed
1688

Akim Demaille's avatar
Akim Demaille committed
1689
1690
## 2015-06-11
### eliminate_state: fixes
Akim Demaille's avatar
Akim Demaille committed
1691
1692
Sometimes there was a mismatch between the state numbers as displayed, and
as expected by `eliminate_state`.  This is fixed.
Akim Demaille's avatar
Akim Demaille committed
1693

Akim Demaille's avatar
Akim Demaille committed
1694
1695
The rendering was nonsensical when all the states were removed.  This is now
fixed.
Akim Demaille's avatar
Akim Demaille committed
1696

Akim Demaille's avatar
Akim Demaille committed
1697
1698
Finally, passing -1 as argument, or no argument at all, delegates the choice
of the state to eliminate to a heuristic.
Akim Demaille's avatar
Akim Demaille committed
1699

1700
1701
1702
1703
1704
1705
1706
1707
## 2015-06-04
### expressions: new identities sets
Rational expressions in Vcsn are "normalized" according to a set of
identities (such that `<0>E => \z` whatever the expression E is).

Vcsn now supports four different sets of identities:

"trivial"
Akim Demaille's avatar
Akim Demaille committed
1708
:   a minimum set of transformations are applied.
1709
1710

"associative"
Akim Demaille's avatar
Akim Demaille committed
1711
1712
:   sum and product are made associative, so `a+(b+c)` and `(a+b)+c` are
    equal.
1713

1714
"linear"
Akim Demaille's avatar
Akim Demaille committed
1715
1716
:   sum is made commutative, and weights are factored, so `a+b+a` is equal
    to `a+b` in B, and to `<2>a+b` in Z.
1717

Akim Demaille's avatar
Akim Demaille committed
1718
"distributive" (or "series")
Akim Demaille's avatar
Akim Demaille committed
1719
1720
:   product and exterior/scalar products are distributed over sum, so
    `[ab]a` is equal to `aa+ba`, and `<2>[ab]` is equal to `<2>a+<2>b`.
1721
1722

Previously the default identities were "associative".  They are now
1723
"linear", to match most users' expectations.
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742

So, for instance we used to report:

    In [2]: c = vcsn.context('lal_char(a-z), z')

    In [3]: c.expression('r+[a-q]')
    Out[3]: r + [a-q]

    In [4]: c.expression('[a-q]+r+r')
    Out[4]: [^s-z] + r

we now report:

    In [3]: c.expression('r+[a-q]')
    Out[3]: [^s-z]

    In [4]: c.expression('[a-q]+r+r')
    Out[4]: [a-q] + <2>r

1743
1744
## 2015-05-29
### nmin: new weightset
Akim Demaille's avatar
Akim Demaille committed
1745
1746
The new tropical semiring ⟨ℕ, +, min⟩ has been introduced. Compared to zmin,
some optimizations can be done, for example in evaluation or in node
Akim Demaille's avatar
Akim Demaille committed
1747
distance where the absence of negative weights allows to trim some branches.
1748

Akim Demaille's avatar
Akim Demaille committed
1749
1750
## 2015-05-26
### cotrie: new algorithm
Akim Demaille's avatar
Akim Demaille committed
1751
1752
1753
1754
In additional to `trie`, which builds a deterministic tree-like automaton
(single initial state, multiple final states), vcsn now supports `cotrie`
which builds a "reversed trie": a codeterministic reversed tree-like
automaton (single final state, multiple initial states).
Akim Demaille's avatar
Akim Demaille committed
1755

Akim Demaille's avatar
Akim Demaille committed
1756
1757
1758
The main feature of `cotrie` is that its result is codeterministic, so it
only takes a determinization to minimize it.  It turns out that in Vcsn
determinization is more efficient than minimization:
Akim Demaille's avatar
Akim Demaille committed
1759
1760
1761
1762
1763
1764
1765
1766
1767

    In [13]: %timeit c.trie('/usr/share/dict/words').minimize()
             1 loops, best of 3: 18.8 s per loop

    In [14]: %timeit c.cotrie('/usr/share/dict/words').determinize()
             1 loops, best of 3: 7.54 s per loop

These automata are isomorphic.

1768
1769
1770
## 2015-05-22
### expressions: output may use label classes
Rational expressions have long supported label classes in input, e.g.,
Akim Demaille's avatar
Akim Demaille committed
1771
1772
1773
1774
[abc0-9].  Polynomials also support them in output.  However expressions
never used classes, which may seriously hinder their readability.  For
instance, to compute an expression describe all words on {a,..., z} except
'hehe', we had:
1775

1776
    In [2]: c = vcsn.context('lal_char(a-z), b')
Akim Demaille's avatar