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:

• Documentation for expression.expansion
• Documentation for expression.derived_term
• Documentation of Vcsn
• Vcsn's web page

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

$(\{\ldots\})^?\to\mathbb{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

$a + b$

e1.star()

$\left(a + b\right)^{*}$

2 * e1 + e1 * e1.star()

$\left\langle 2 \right\rangle \,\left(a + b\right) + \left(a + b\right) \, \left(a + b\right)^{*}$

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

$a \odot \left[b\right]$

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

$\left\langle 1\right\rangle \oplus a \odot \left[\left(a + b\right)^{*}\right] \oplus b \odot \left[\left(a + b\right)^{*}\right]$

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

$\varepsilon \odot \left[a \, b \oplus \left(a + b\right)^{*} \backslash b\right]$

x1 // x2

$\varepsilon \odot \left[a \, b \backslash \varepsilon \oplus b \backslash \left(a + b\right)^{*}\right]$

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

$\left\langle 2 \right\rangle \,\left(a + b\right)^{*}$

e.constant_term()

$2$

e.derivation('a')

$\left\langle 2\right\rangle \left(a + b\right)^{*}$

e.derivation('b')

$\left\langle 2\right\rangle \left(a + b\right)^{*}$

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

e.expansion()

$\left\langle 2\right\rangle \oplus a \odot \left[\left\langle 2\right\rangle \left(a + b\right)^{*}\right] \oplus b \odot \left[\left\langle 2\right\rangle \left(a + b\right)^{*}\right]$

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

$\left\langle 11 \right\rangle \,\left(a \, {b}^{*}\right) + \left\langle 2 \right\rangle \,a \backslash \left( \left\langle 3 \right\rangle \,\left(a + b\right) + \left\langle 5 \right\rangle \,\left(a \, {a}^{*}\right) + \left\langle 7 \right\rangle \,\left(a \, {b}^{*}\right)\right)$

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

e1.expansion()

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

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

$\left( \left\langle \frac{1}{2} \right\rangle \,\left(a \, b\right) \backslash a \, {b}^{*}\right)^{*}$

e.expansion()

$\left\langle 1\right\rangle \oplus \varepsilon \odot \left[\left\langle \frac{1}{2}\right\rangle \left(b \backslash {b}^{*}\right) \, \left( \left\langle \frac{1}{2} \right\rangle \,\left(a \, b\right) \backslash a \, {b}^{*}\right)^{*}\right]$

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()

$\left\langle 2 \right\rangle \,\varepsilon + \left\langle 2 \right\rangle \,\left(b \, \left( \left\langle 2 \right\rangle \,b\right)^{*}\right)$

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

$1$

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

$(\{\ldots\})^?\to\mathbb{B}$

w = B.weight('1')
w

$\top$

w.star()

$\top$

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

${\left(a \, b \, c\right)^{*}}^{T}$

e.expansion()

$\left\langle 1\right\rangle \oplus c \odot \left[\left(a \, b\right)^{T} \, {\left(a \, b \, c\right)^{*}}^{T}\right]$

e.derived_term()

Then with a right quotient.

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

$\left(\left(b \, a\right)^{T} \backslash \left(a \, b \, a\right)^{T}\right)^{T}$

e.derived_term()

Example 7

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

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

$\left({\left(a + b\right)^{*}}^{T} \backslash \left(a \, b\right)^{T}\right)^{T}$

a = e.derived_term()
a

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