expression.expansion.ipynb

Kernel: Python 3

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

References:

• demaille.2016.ictac introduces expansions

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(e, ss):
    eqs = [r'd\left({0:x}\right) &= {1:x}'.format(e, e.expansion()),
           r'c\left({0:x}\right) &= {1:x}'.format(e, e.constant_term())]
    for s in ss:
        eqs.append(r'\frac{{\partial}}{{\partial {0}}} {1:x} &= {2:x}'
                   .format(s, e, e.derivation(s)))
    return Latex(r'''\begin{{aligned}}
        {eqs}
    \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.

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

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

diffs(e, ['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.

q = vcsn.context('lal_char(abc), q')
e = q.expression('(<1/6>a*+<1/3>b*)*')
diffs(e, ['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.

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

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

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

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

e.derived_term()