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.
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.
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.
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.
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
.
Derivative
Although not covered in the paper, Vcsn does support the derivatives. However, the quotient operator is not supported.
Those three facts, constant term and derivative wrt and , are fully captured by this expansion.
Example : 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 is therefore:
Its expansion is (contrary to the paper, the empty expression is denoted instead of ):
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:
The derived-term automaton of , , is:
Example 5: Not all the States are Coaccessible
As such, this automaton in is invalid: it contains a spontaneous loop whose weight, 1, is not starrable.
Once trimmed, it is valid though, and its spontaneous transitions may be removed.
A (basic) rational expression is therefore:
Example 6
The following expression in invalid in , but valid in .
This is because the weight of the spontaneous cycle, 1, is not starrable:
But in , it is well defined (Vcsn uses to denote True, and for False):
Hence the automaton is valid.
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.
Then with a right quotient.
Example 7
The following example, in , computes the suffixes of the language .