Compute the expansion of a weighted expression. An expansion is a structure that combines three different features of a (weighted) rational expression $r$:

  • its constant-term, i.e., the weight associated to the empty word, denoted $c(r)$
  • its firsts, i.e., the set of labels that prefix the defined language, denoted $f(r)$
  • its derived-terms, i.e., for each label $a$, its associated polynomials of "subsequent" expressions, denoted $\frac{\partial}{\partial a}r$.

If one denotes $d(r)$ the expansion of $r$, it holds that: $$ d(r) = c(r) \oplus \bigoplus_{a \in f(r)} a \odot \frac{\partial}{\partial a}r $$

The main use of expansions (and derivations) is to compute the derived-term automaton of an expression. The advantage of expansions over derivations is their independence with respect to the alphabet. As a matter of fact, they do not require a finite-alphabet (see examples below). Besides, the reunite constant-term, first, and derivation into a single concept.

See also:


The following function will prove handy to demonstrate the relation between the expansion on the one hand, and, on the other hand, the constant-term and the derivations. It takes an expression $r$ and a list of letters, and returns a $\LaTeX$ aligned environment to display:

  1. $d(r)$ the expansion
  2. $c(r)$ the constant-term
  3. $\frac{\partial}{\partial a}r$ the derivation with respect to $a$.
In [1]:
import vcsn
from IPython.display import Latex

def diffs(r, ss):
    eqs = [r'd\left({0}\right) &= {1}'.format(r.format('latex'), r.expansion().format('latex')),
           r'c\left({0}\right) &= {1}'.format(r.format('latex'), r.constant_term().format('latex'))]
    for s in ss:
        eqs.append(r'\frac{{\partial}}{{\partial {0}}} {1} &= {2}'
    return Latex(r'''\begin{{aligned}}
    \end{{aligned}}'''.format(eqs = r'\\'.join(eqs)))

Classical Expressions

In the classical case (labels are letters, and weights are Boolean), this is the construct as described by Antimirov.

In [2]:
b = vcsn.context('lal_char(ab), b')
r = b.expression('[ab]{3}')
$a \odot \left[\left(a + b\right)^{2}\right] \oplus b \odot \left[\left(a + b\right)^{2}\right]$

Or, using the diffs function we defined above:

In [3]:
diffs(r, ['a', 'b'])
\begin{aligned} d\left(\left(a + b\right)^{3}\right) &= a \odot \left[\left(a + b\right)^{2}\right] \oplus b \odot \left[\left(a + b\right)^{2}\right]\\c\left(\left(a + b\right)^{3}\right) &= \bot\\\frac{\partial}{\partial a} \left(a + b\right)^{3} &= \left(a + b\right)^{2}\\\frac{\partial}{\partial b} \left(a + b\right)^{3} &= \left(a + b\right)^{2} \end{aligned}

Weighted Expressions

Of course, expressions can be weighted.

In [4]:
q = vcsn.context('lal_char(abc), q')
r = q.expression('(<1/6>a*+<1/3>b*)*')
diffs(r, ['a', 'b'])
\begin{aligned} d\left(\left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\right) &= \left\langle 2\right\rangle \oplus a \odot \left[\left\langle \frac{1}{3}\right\rangle {a}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\right] \oplus b \odot \left[\left\langle \frac{2}{3}\right\rangle {b}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\right]\\c\left(\left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\right) &= 2\\\frac{\partial}{\partial a} \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*} &= \left\langle \frac{1}{3}\right\rangle {a}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\\\frac{\partial}{\partial b} \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*} &= \left\langle \frac{2}{3}\right\rangle {b}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*} \end{aligned}

And this is tightly connected with the construction of the derived-term automaton.

In [5]:
%3 I0 0 (⟨1/6⟩a*+⟨1/3⟩b*)* I0->0 F0 F1 F2 0->F0 ⟨2⟩ 1 a*(⟨1/6⟩a*+⟨1/3⟩b*)* 0->1 ⟨1/3⟩a 2 b*(⟨1/6⟩a*+⟨1/3⟩b*)* 0->2 ⟨2/3⟩b 1->F1 ⟨2⟩ 1->1 ⟨4/3⟩a 1->2 ⟨2/3⟩b 2->F2 ⟨2⟩ 2->1 ⟨1/3⟩a 2->2 ⟨5/3⟩b

Breaking expansion

There is (currently) no means to break an expansion (which would mean breaking its polynomials). The construction of the derived-term automaton does it on the fly.

Non-free labelsets

Contrary to derivation, which requires a finite alphabet, expansions support labels which are words, or even tuples.

Below, we define a two-tape-of-words context, and a simple expression that uses three different multitape labels: $(\mathrm{11}|\mathrm{eleven})$, etc. Then derived_term is used to build the automaton.

In [6]:
ctx = vcsn.context('lat<law_char(0-9), law_char(a-zA-Z)>, b')
$\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}^* \times \{A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\}^*\to\mathbb{B}$
In [7]:
r = ctx.expression("(11|eleven+12|twelve+13|thirteen)*")
$\left(\mathit{11}|\mathit{eleven} + \mathit{12}|\mathit{twelve} + \mathit{13}|\mathit{thirteen}\right)^{*}$
In [8]:
$\left\langle \top\right\rangle \oplus \mathit{11}|\mathit{eleven} \odot \left[\left(\mathit{11}|\mathit{eleven} + \mathit{12}|\mathit{twelve} + \mathit{13}|\mathit{thirteen}\right)^{*}\right] \oplus \mathit{12}|\mathit{twelve} \odot \left[\left(\mathit{11}|\mathit{eleven} + \mathit{12}|\mathit{twelve} + \mathit{13}|\mathit{thirteen}\right)^{*}\right] \oplus \mathit{13}|\mathit{thirteen} \odot \left[\left(\mathit{11}|\mathit{eleven} + \mathit{12}|\mathit{twelve} + \mathit{13}|\mathit{thirteen}\right)^{*}\right]$

This enables the construction of the associated derived-term automaton.

In [9]:
%3 I0 0 (11|eleven+12|twelve+13|thirteen)* I0->0 F0 0->F0 0->0 11|eleven, 12|twelve, 13|thirteen