automaton.lightest(num=1, algo="auto")

Return a (finite) approximation of the behavior of the automaton. In other words, compute the polynomial of the lightest accepted words (according to the shortlex order), and their associated weight.

Arguments:

• num the number of words to find (there might be fewer).
• algo the algorithm name.

The algorithm can be:

• "breadth-first": uses the same algorithm as for the search of multiple words.
• "yen": uses yen algorithm to retrieve multiple paths, the algorithm does not count loops as possible paths.
• The different implementations of lightest path (see lightest_automaton): if num is different from one it will use the default implementation of lightest.
  • "auto"
  • "a-star"
  • "bellman-ford"
  • "dijkstra"

Preconditions:

• None

See also:

• automaton.shortest
• automaton.lightest_automaton

Examples

import vcsn

%%automaton --strip bin
context = "lal_char, nmin"
$ -> 0
0 -> 1 <6>a
0 -> 2 <1>a
2 -> 3 <1>b
3 -> 3 <2>b
3 -> 4 <1>c
4 -> 1 <1>d
0 -> 5 <2>a
5 -> 1 <3>b
1 -> $

bin.lightest()

$\left\langle 4\right\rangle \mathit{abcd}$

Note that polynomials are printed in shortlex order, i.e., an order based on the labels, although here, a weight-based order would make more sense.

bin.lightest(2)

$\left\langle 5\right\rangle \mathit{ab} \oplus \left\langle 4\right\rangle \mathit{abcd}$

bin.lightest(10)

$\left\langle 6\right\rangle \mathit{a} \oplus \left\langle 5\right\rangle \mathit{ab} \oplus \left\langle 4\right\rangle \mathit{abcd} \oplus \left\langle 6\right\rangle \mathit{abbcd} \oplus \left\langle 8\right\rangle \mathit{abbbcd} \oplus \left\langle 10\right\rangle \mathit{abbbbcd} \oplus \left\langle 12\right\rangle \mathit{abbbbbcd} \oplus \left\langle 14\right\rangle \mathit{abbbbbbcd} \oplus \left\langle 16\right\rangle \mathit{abbbbbbbcd} \oplus \left\langle 18\right\rangle \mathit{abbbbbbbbcd}$