Quotient Operators for Weighted Rational Expressions

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

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.

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]:
%3 I0 0 ⟨11⟩(ab*)+⟨2⟩a{\}(⟨3⟩(a+b)+⟨5⟩(aa*)+⟨7⟩(ab*)) I0->0 F0 F1 F2 0->F0 ⟨6⟩ 1 a* 0->1 ⟨10⟩ε 2 b* 0->2 ⟨14⟩ε, ⟨11⟩a 1->F1 1->1 a 2->F2 2->2 b

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]:
%3 I0 0 (⟨1/2⟩(ab){\}ab*)* I0->0 F0 F2 0->F0 1 (b{\}b*)(⟨1/2⟩(ab){\}ab*)* 0->1 ⟨1/2⟩ε 2 b*(⟨1/2⟩(ab){\}ab*)* 1->2 ε 3 (b{\}ε)(⟨1/2⟩(ab){\}ab*)* 1->3 ε 2->F2 2->1 ⟨1/2⟩ε 2->2 b 3->3 ε

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]:
%3 I0 0 (⟨1/2⟩(ab){\}ab*)* I0->0 F0 F2 0->F0 1 (b{\}b*)(⟨1/2⟩(ab){\}ab*)* 0->1 ⟨1/2⟩ε 2 b*(⟨1/2⟩(ab){\}ab*)* 1->2 ε 2->F2 2->1 ⟨1/2⟩ε 2->2 b
In [23]:
a.trim().proper()
Out[23]:
%3 I0 0 0 I0->0 F0 F1 0->F0 ⟨2⟩ 1 1 0->1 b 1->F1 ⟨2⟩ 1->1 ⟨2⟩b

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]:
%3 I0 0 (ab{\}ab)* I0->0 F0 F1 0->F0 1 (b{\}b)(ab{\}ab)* 0->1 ε 1->F1 1->1 ε
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]:
%3 I0 0 (ab{\}ab)* I0->0 F0 F1 0->F0 1 (b{\}b)(ab{\}ab)* 0->1 ε 1->F1 1->1 ε
In [33]:
a.is_valid()
Out[33]:
True
In [34]:
a.proper()
Out[34]:
%3 I0 0 0 I0->0 F0 0->F0

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]:
%3 I0 0 (abc)*ᵗ I0->0 F0 0->F0 1 (ab)ᵗ(abc)*ᵗ 0->1 c 2 a(abc)*ᵗ 1->2 b 2->0 a

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]:
%3 I0 0 ((ba)ᵗ{\}(aba)ᵗ)ᵗ I0->0 F3 1 (b{\}(ab)ᵗ)ᵗ 0->1 ε 2 a 1->2 ε 3 ε 2->3 a 3->F3

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]:
%3 I0 0 ((a+b)*ᵗ{\}(ab)ᵗ)ᵗ I0->0 F4 F7 1 (ba)ᵗ 0->1 ε 2 ((a+b)*ᵗ{\}a)ᵗ 0->2 ε 8 b 1->8 a 3 a 2->3 ε 4 ((a+b)*ᵗ{\}ε)ᵗ 2->4 ε 7 ε 3->7 a 4->F4 5 (a(a+b)*ᵗ{\}ε)ᵗ 4->5 ε 6 (b(a+b)*ᵗ{\}ε)ᵗ 4->6 ε 5->5 ε 6->6 ε 7->F7 8->7 b
In [42]:
a.trim().proper().determinize().minimize()
Out[42]:
%3 I0 0 {0} I0->0 F0 F1 F2 0->F0 1 {1, 2} 0->1 a 1->F1 2 {1} 1->2 b 2->F2