Quotient Operators for Weighted Rational Expressions¶

This page is a complement to our submission to ICTAC 2017. This page exists in several forms:

A Dynamic Notebook, which can be edited, played with
A static HTML page, whose graphical rendering is always correct.

More information is available here:

You may change the cells, and run then. To run a cell in a notebook, hit "Control-Enter" (in which case the focus stays on the same cell) or "Shift-Enter" (focus goes to the next cell). Beware that depending on the requested operations, Vcsn may generate and compile code, which may be a really slow process on small machines (about a minute): be patient! However, the code is compiled only once: successive uses will be way faster.

To run all the cells anew, select "Restart & Run All" in the "Kernel" menu above.

import sys
import vcsn

Section 2, Notations¶

First we introduce the "context" we are interested in: labels are letter-or-empty-word ("lan": labels are nullable), values are rational numbers.

Q = vcsn.context('lan, q')
Q

Expressions¶

The rational expressions in Vcsn supports several operators beyond the classical ones. See Expressions for all the details. The following examples should be self-explanatory.

e1 = Q.expression('[ab]'); e1

e1.star()

2 * e1 + e1 * e1.star()

Expansions¶

One can play with the different operations on expansions. However, there is no direct means to enter an expansion, one has to compute the expansion of an expression.

e1 = Q.expression('ab')
x1 = e1.expansion()
x1

e2 = Q.expression('[ab]*')
x2 = e2.expansion()
x2

The left-quotient is denoted {\} in the syntax of Vcsn's expressions, but we use Python's operator // to denote it. So e // f denotes e {\} f.

x2 // x1

x1 // x2

Derivative¶

Although not covered in the paper, Vcsn does support the derivatives. However, the quotient operator is not supported.

e = Q.expression('<2>[ab]*')
e

e.constant_term()

e.derivation('a')

e.derivation('b')

Those three facts, constant term and derivative wrt $a$ and $b$, are fully captured by this expansion.

e.expansion()

Example $\mathsf{E}_1$: A Simple Expression¶

In Vcsn, the left-quotient is written {\} (because the backslash character is used to escape operators, e.g., \* denotes the letter *, not the Kleene star). The expression $\mathsf{E}_1$ is therefore:

e1 = Q.expression('(<2>a) {\} (<3>[ab] + <5>aa* + <7>ab*) + <11>ab*')
e1

Its expansion is (contrary to the paper, the empty expression is denoted $\varepsilon$ instead of $\mathsf{1}$):

e1.expansion()

For sake of performance, the constant term is actually kept separate in our implementation of expansions. The previous result, rewritten in the style of the paper, is exactly the same:

$$ \left\langle 6\right\rangle \oplus \varepsilon \odot \left[\left\langle 10\right\rangle {a}^{*} \oplus \left\langle 14\right\rangle {b}^{*}\right] \oplus a \odot \left[\left\langle 11\right\rangle {b}^{*}\right] = \varepsilon \odot \left[ \left\langle 6\right\rangle \odot \varepsilon \oplus \left\langle 10\right\rangle \odot {a}^{*} \oplus \left\langle 14\right\rangle \odot {b}^{*}\right] \oplus a \odot \left[\left\langle 11\right\rangle \odot {b}^{*}\right] $$

The derived-term automaton of $\mathsf{E}_1$, $\mathcal{A}_{\mathsf{E}_1}$, is:

a1 = e1.derived_term()
a1

Example 5: Not all the States are Coaccessible¶

e = Q.expression('(<1/2>ab {\} ab*)*')
e

e.expansion()

a = e.derived_term()
a

As such, this automaton in $\mathbb{Q}$ is invalid: it contains a spontaneous loop whose weight, 1, is not starrable.

a.is_valid()

False

Once trimmed, it is valid though, and its spontaneous transitions may be removed.

a.trim()

a.trim().proper()

A (basic) rational expression is therefore:

a.trim().proper().expression()

Example 6¶

The following expression in invalid in $\mathbb{Q}$, but valid in $\mathbb{B}$.

e = Q.expression('(ab {\} ab)*')
a = e.derived_term()
a

a.is_valid()

False

This is because the weight of the spontaneous cycle, 1, is not starrable:

w = Q.weight('1')
w

try:
    w.star()
except RuntimeError as e:
    print(e, file=sys.stderr)

Q: value is not starrable: 1

But in $\mathbb{B}$, it is well defined (Vcsn uses $\top$ to denote True, and $\bot$ for False):

B = vcsn.context('lan, b')
B

w = B.weight('1')
w

w.star()

Hence the automaton is valid.

e = B.expression('(ab {\} ab)*')
a = e.derived_term()
a

a.is_valid()

True

a.proper()

Section 5: Transpose and Right Quotient¶

The right quotient is written as {/}, and transpose as a postfix operator {T}.

The following simple example shows how transpose is handled.

e = Q.expression('(abc)*{T}')
e

e.expansion()

e.derived_term()

Then with a right quotient.

e = Q.expression('aba {/} ba')
e

e.derived_term()

Example 7¶

The following example, in $\mathbb{B}$, computes the suffixes of the language $ab$.

e = B.expression('(ab){/}[ab]*')
e

a = e.derived_term()
a

a.trim().proper().determinize().minimize()