expression
.derived_term(
algo
="expansion",
lazy
=False,
deterministic
=False,
breaking
=False)
Generate the derived-term automaton from an expression.
The arguments are:
algo
:"derivation"
: rely on theexpression.derivation
."expansion"
: rely on theexpression.expansion
.
lazy
: whether to build the result lazily, on the flydeterministic
: whether to build a deterministic automaton.breaking
:split
the polynomials at each step
Preconditions:
derivation-based algorithms require a free labelset (e.g., word labels are not supported)
deterministic
might not terminate on some expressions (in which case considerlazy
)expressions with complement operators might not terminate either
Also known as:
Antimirov automaton
equation automaton
partial-derivatives automaton
See also:
References:
antimirov.1996.tcs introduces the concept of derived-term automaton
lombardy.2005.tcs defines the derived-term construction for weighted automata (and coins the name "derived-term").
angrand.2010.jalc defines its breaking variant
demaille.2016.ictac introduces support for conjunction and complement
Examples
Classical Expressions
In the classical case (labels are letters, and weights are Boolean), this is the construct as described by Antimirov.
The states of the resulting automaton are decorated by their expressions. This can be stripped:
The result does not depend on the core computation: expansions and derivations compute the same terms:
Deterministic Automata
Alternatively, one can request a deterministic result:
Extended Rational Expressions
Extended expressions are supported. For instance, words starting with a
s and then b
s, but not exactly ab
:
Weighted Expressions
The following example is taken from lombardy.2005.tcs:
Multitape Expressions
Since both expansions and derivatives in Vcsn support the tuple operator, both flavors of derived_term
can be used to build a multitape automaton from a multitape expression. For instance:
Broken derived-term automaton
"Breaking" variants of derivation and expansion "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.
Lazy construction
The derived-term automaton can be built on-the-fly, on-demand: states are uncovered on needed (e.g., when traversed by an evaluation). This is especially useful when considering an expression on which the process does not terminate (i.e., would generate an "infinite" automaton).
The following expression does not admit a (finite) deterministic automaton (and determinizing the non-deterministic derived-term automaton would not terminate either). Repeatedly calling the evaluation uncovers portions of an "infinite" deterministic automaton.
Note that lazy determinization is also available: see automaton.determinize to see the corresponding example.
Since it entails a "local" determinization ("under" the complement operator), the algorithm fails would not terminate.