# Quotient Operators for Weighted Rational Expressions¶

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.

In [1]:
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.

In [2]:
Q = vcsn.context('lan, q')
Q

Out[2]:
$(\{\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.

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

Out[3]:
$a + b$
In [4]:
e1.star()

Out[4]:
$\left(a + b\right)^{*}$
In [5]:
2 * e1 + e1 * e1.star()

Out[5]:
$\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.

In [6]:
e1 = Q.expression('ab')
x1 = e1.expansion()
x1

Out[6]:
$a \odot \left[b\right]$
In [7]:
e2 = Q.expression('[ab]*')
x2 = e2.expansion()
x2

Out[7]:
$\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.

In [8]:
x2 // x1

Out[8]:
$\varepsilon \odot \left[a \, b \oplus \left(a + b\right)^{*} \backslash b\right]$
In [9]:
x1 // x2

Out[9]:
$\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.

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

Out[10]:
$\left\langle 2 \right\rangle \,\left(a + b\right)^{*}$
In [11]:
e.constant_term()

Out[11]:
$2$
In [12]:
e.derivation('a')

Out[12]:
$\left\langle 2\right\rangle \left(a + b\right)^{*}$
In [13]:
e.derivation('b')

Out[13]:
$\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.

In [14]:
e.expansion()

Out[14]:
$\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:

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

Out[15]:
$\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}$):

In [16]:
e1.expansion()

Out[16]:
$\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:

In [17]:
a1 = e1.derived_term()
a1

Out[17]:

## Example 5: Not all the States are Coaccessible¶

In [18]:
e = Q.expression('(<1/2>ab {\} ab*)*')
e

Out[18]:
$\left( \left\langle \frac{1}{2} \right\rangle \,\left(a \, b\right) \backslash a \, {b}^{*}\right)^{*}$
In [19]:
e.expansion()

Out[19]:
$\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]$
In [20]:
a = e.derived_term()
a

Out[20]:

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

In [21]:
a.is_valid()

Out[21]:
False

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

In [22]:
a.trim()

Out[22]:
In [23]:
a.trim().proper()

Out[23]:

A (basic) rational expression is therefore:

In [24]:
a.trim().proper().expression()

Out[24]:
$\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}$.

In [25]:
e = Q.expression('(ab {\} ab)*')
a = e.derived_term()
a

Out[25]:
In [26]:
a.is_valid()

Out[26]:
False

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

In [27]:
w = Q.weight('1')
w

Out[27]:
$1$
In [28]:
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):

In [29]:
B = vcsn.context('lan, b')
B

Out[29]:
$(\{\ldots\})^?\to\mathbb{B}$
In [30]:
w = B.weight('1')
w

Out[30]:
$\top$
In [31]:
w.star()

Out[31]:
$\top$

Hence the automaton is valid.

In [32]:
e = B.expression('(ab {\} ab)*')
a = e.derived_term()
a

Out[32]:
In [33]:
a.is_valid()

Out[33]:
True
In [34]:
a.proper()

Out[34]:

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

In [35]:
e = Q.expression('(abc)*{T}')
e

Out[35]:
${\left(a \, b \, c\right)^{*}}^{T}$
In [36]:
e.expansion()

Out[36]:
$\left\langle 1\right\rangle \oplus c \odot \left[\left(a \, b\right)^{T} \, {\left(a \, b \, c\right)^{*}}^{T}\right]$
In [37]:
e.derived_term()

Out[37]:

Then with a right quotient.

In [38]:
e = Q.expression('aba {/} ba')
e

Out[38]:
$\left(\left(b \, a\right)^{T} \backslash \left(a \, b \, a\right)^{T}\right)^{T}$
In [39]:
e.derived_term()

Out[39]:

### Example 7¶

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

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

Out[40]:
$\left({\left(a + b\right)^{*}}^{T} \backslash \left(a \, b\right)^{T}\right)^{T}$
In [41]:
a = e.derived_term()
a

Out[41]:
In [42]:
a.trim().proper().determinize().minimize()

Out[42]: