expression.expansion()

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:

• expression.constant_term
• expression.derivation
• expression.derived_term

Examples

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

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}'
                   .format(s,
                           r.format('latex'),
                           r.derivation(s).format('latex')))
    return Latex(r'''\begin{{aligned}}
        {eqs}
    \end{{aligned}}'''.format(eqs = r'\\'.join(eqs)))

:0: FutureWarning: IPython widgets are experimental and may change in the future.

Classical Expressions

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

b = vcsn.context('lal_char(ab), b')
r = b.expression('[ab]{3}')
r.expansion()

$a \odot \left[\left(a + b\right) \, \left(a + b\right)\right] \oplus b \odot \left[\left(a + b\right) \, \left(a + b\right)\right]$

Or, using the diffs function we defined above:

diffs(r, ['a', 'b'])

\begin{aligned} d\left(\left(a + b\right) \, \left(a + b\right) \, \left(a + b\right)\right) &= a \odot \left[\left(a + b\right) \, \left(a + b\right)\right] \oplus b \odot \left[\left(a + b\right) \, \left(a + b\right)\right]\\c\left(\left(a + b\right) \, \left(a + b\right) \, \left(a + b\right)\right) &= \bot\\\frac{\partial}{\partial a} \left(a + b\right) \, \left(a + b\right) \, \left(a + b\right) &= \left(a + b\right) \, \left(a + b\right)\\\frac{\partial}{\partial b} \left(a + b\right) \, \left(a + b\right) \, \left(a + b\right) &= \left(a + b\right) \, \left(a + b\right) \end{aligned}

Weighted Expressions

Of course, expressions can be weighted.

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.

r.derived_term()

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.

ctx = vcsn.context('lat<law_char(0-9), law_char(a-zA-Z)>, b')
ctx

$\{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\}^*\rightarrow\mathbb{B}$

r = ctx.expression("(11|eleven+12|twelve+13|thirteen)*")
r

$\left(\mathit{11}|\mathit{eleven} + \mathit{12}|\mathit{twelve} + \mathit{13}|\mathit{thirteen}\right)^{*}$

r.expansion()

$\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.

r.derived_term()