Derived-term Automata for Extended Weighted Rational Expressions
This page is a complement to Derived-term Automata for Extended Weighted Rational Expressions presented at ICTAC 2016. 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.
Valid Expressions
Beware that the so-called ''context'' (which, in Vcsn parlance denotes the type of labels (letters or words, etc.) and the semiring of weights) has an extreme importance. In particular, an expression might be valid in a given context, and invalid in another.
As an example, is valid in , so we can build its derived-term automaton.
However, the construction will fail in , since the constant term for is 1, which is not starrable in (indeed, is not a value in ).
Example : A Lex-like Scanner
Desugaring
We introduce the "context" (i.e., the automaton type) that corresponds to labels that are letters (lal_char
) and weights that are rational numbers (q
).
Vcsn supports the <+
operator. It is desugared in a combination of conjuction and complement.
The Derived-Term Automaton
The expansion and the derived-term automaton of follow.
Example : A Simple Expression
Polynomials and Derivatives
The derivatives of with respect to and are the following polynomials.
The expansion of is as follows. The notation is slightly different from the paper, where for higher clarity the weights in the polynomials are separated from the expressions by a . In the implementation, since the weight is always displayed, this separation is useless, and not put, for conciseness.
The Derived-Term Automaton
The derived-term automaton can be computed using derivations or expansions.
The Deterministic Derived-Term Automaton
Section 4.2: An Infinite Automaton
There exists no finite weighted deterministic automaton for the following expression.
Repeated evaluations uncover parts of this automaton.
Section 5: Related Work
Additional Operators
The following automata demonstrate the support of the shuffle operator (denoted ':
' in ASCII, and '' in ), and the infiltrate operator ('&:
' and ''). See also the documentation of the corresponding operations on automata: automaton.shuffle and automaton.infiltrate.
The 'trivial'
argument above restricts the identities to the trivial ones, otherwise additional identities would defeat our attempt to "taint" the a
s below:
Broken Derived Terms
"Breaking" variants "split" the polynomials at each step. In short, it means that no state will be labeled by an addition: rather the addition is split into several states. As a consequence, the automaton might have several initial states.