polynomial.cotrie

Generate a "cotrie" automaton (multiple initial state, single final state automaton: a reversed tree) from a finite series, given as a polynomial of words.

Postconditions:

  • Result.is_codeterministic()
  • Result = p.cotrie.shortest(N) for a large enough N.

See also:

Examples

In [1]:
import vcsn

Boolean weights (finite language)

In [2]:
language = '\e+a+b+abc+abcd+abdc'

b = vcsn.context('lal_char, b')
B = vcsn.context('law_char, b')

B.polynomial(language).trie()
Out[2]:
%3 I0 0 0 I0->0 F0 F1 F2 F4 F5 F7 0->F0 1 1 0->1 a 2 2 0->2 b 1->F1 3 3 1->3 b 2->F2 4 4 3->4 c 6 6 3->6 d 4->F4 5 5 4->5 d 5->F5 7 7 6->7 c 7->F7
In [3]:
B.polynomial(language).cotrie()
Out[3]:
%3 I0 0 0 I0->0 I1 1 1 I1->1 I2 2 2 I2->2 I5 5 5 I5->5 I9 9 9 I9->9 I12 12 12 I12->12 F0 0->F0 1->0 a 2->0 b 3 3 3->0 c 4 4 4->3 b 5->4 a 6 6 6->0 d 7 7 7->6 c 8 8 8->7 b 9->8 a 10 10 10->3 d 11 11 11->10 b 12->11 a

Since the cotrie is codeterministic, determinizing it suffices to minimize it. It turns out that in the current implementation of Vcsn, it is faster to determinize than to minimize:

In [4]:
%timeit B.polynomial(language).trie().minimize()

10000 loops, best of 3: 71.5 µs per loop
In [5]:
%timeit B.polynomial(language).cotrie().determinize()

10000 loops, best of 3: 39.6 µs per loop
In [6]:
a1 = B.polynomial(language).trie().minimize()
a2 = B.polynomial(language).cotrie().determinize()
a1.is_isomorphic(a2)
Out[6]:
True