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:

Examples

In [1]:
import vcsn
In [2]:
%%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 -> $
%3 I0 0 0 I0->0 ⟨0⟩ F1 1 1 0->1 ⟨6⟩a 2 2 0->2 ⟨1⟩a 5 5 0->5 ⟨2⟩a 1->F1 ⟨0⟩ 3 3 2->3 ⟨1⟩b 3->3 ⟨2⟩b 4 4 3->4 ⟨1⟩c 4->1 ⟨1⟩d 5->1 ⟨3⟩b
In [3]:
bin.lightest()
Out[3]:
$\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.

In [4]:
bin.lightest(2)
Out[4]:
$\left\langle 5\right\rangle \mathit{ab} \oplus \left\langle 4\right\rangle \mathit{abcd}$
In [5]:
bin.lightest(10)
Out[5]:
$\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}$