polynomial.trie

Generate a "trie" automaton (a prefix tree) from a finite series, given as a polynomial of words.

Postconditions:

  • Result.is_deterministic()
  • Result = p.trie.shortest(N) for a large enough N.

Properties:

  • The support of result is isomorphic to the support of determinized standard automaton built from the polynomials seen as a rational expression, however weights are not placed at the same locations.

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.expression(language).standard().determinize().strip()
Out[3]:
%3 I0 0 0 I0->0 F0 F1 F2 F4 F6 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 5 5 3->5 d 4->F4 7 7 4->7 d 6 6 5->6 c 6->F6 7->F7

Weighted polynomials of words (finite series)

In [4]:
series = '<2>\e + <3>a + <4>b + <5>abc + <6>abcd + <7>abdc'

q = vcsn.context('lal_char, z')
Q = vcsn.context('law_char, z')

Q.polynomial(series).trie()
Out[4]:
%3 I0 0 0 I0->0 F0 F1 F2 F4 F5 F7 0->F0 ⟨2⟩ 1 1 0->1 a 2 2 0->2 b 1->F1 ⟨3⟩ 3 3 1->3 b 2->F2 ⟨4⟩ 4 4 3->4 c 6 6 3->6 d 4->F4 ⟨5⟩ 5 5 4->5 d 5->F5 ⟨6⟩ 7 7 6->7 c 7->F7 ⟨7⟩
In [5]:
q.expression(series).standard().determinize().strip()
Out[5]:
%3 I0 0 0 I0->0 F0 F1 F2 F4 F6 F7 0->F0 ⟨2⟩ 1 1 0->1 a 2 2 0->2 ⟨4⟩b 1->F1 ⟨3⟩ 3 3 1->3 b 2->F2 4 4 3->4 c 5 5 3->5 ⟨7⟩d 4->F4 ⟨5⟩ 6 6 4->6 ⟨6⟩d 7 7 5->7 c 6->F6 7->F7