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, see Notes).
  • algo the algorithm name.

The algorithm can be:

  • "breadth-first": uses the same algorithm as for the search of multiple words.
  • "yen": uses Yen's algorithm to retrieve multiple paths, the algorithm does not count loops as possible paths.
  • "eppstein": uses Eppstein's algorithm to retrieve multiple paths on any automata.
  • "auto": Same as "breadth-first" for any k different from 1 (see lightest_automaton otherwise).
  • 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"

Notes:

  • Lightest computations find lightest paths in the automaton by selecting the K lightest accepting sequences of states in the automaton, regardless of the accepting words. These paths might add up in the resulting polynomial if they represent the same word. Hence, resulting in fewer results than expected. Consider for instance a naive automaton for <+1>a + <-1>a: it would find <-1>a although a is not accepted. This problem will not happen if the automaton is unambiguous, a property that can be verified using automaton.is_ambiguous.

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}$

Other algorithms can be called by specifying a second argument to the function.

Note that Yen's algorithm requires the automaton to have no cycles, as demonstrated here.

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