expression.derived_term.ipynb

Kernel: Python 3

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 the expression.derivation.

  • "expansion": rely on the expression.expansion.

• lazy: whether to build the result lazily, on the fly

• deterministic: 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 consider lazy)

• expressions with complement operators might not terminate either

Also known as:

• Antimirov automaton

• equation automaton

• partial-derivatives automaton

See also:

• expression.automaton

• expression.constant_term

• expression.derivation

• expression.expansion

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.

import vcsn
bexp = vcsn.B.expression
r = bexp('[ab]*a[ab]{3}')
a = r.derived_term()
a

The states of the resulting automaton are decorated by their expressions. This can be stripped:

a.strip()

The result does not depend on the core computation: expansions and derivations compute the same terms:

r.derived_term('derivation')

Deterministic Automata

Alternatively, one can request a deterministic result:

qexp = vcsn.Q.expression
r = qexp('aba+a(a+<-1>ba)')
nfa = r.derived_term()
nfa

dfa = r.derived_term(deterministic=True)
dfa

nfa.determinize()

Extended Rational Expressions

Extended expressions are supported. For instance, words starting with as and then bs, but not exactly ab:

r = bexp('a*b* & (ab){c}')
r

${a}^{*} \, {b}^{*} \& \left(a \, b\right)^{c}$

a = r.derived_term()
a

a.shortest(10)

$\varepsilon \oplus \mathit{a} \oplus \mathit{b} \oplus \mathit{aa} \oplus \mathit{bb} \oplus \mathit{aaa} \oplus \mathit{aab} \oplus \mathit{abb} \oplus \mathit{bbb} \oplus \mathit{aaaa}$

Weighted Expressions

The following example is taken from lombardy.2005.tcs:

r = qexp('(<1/6>a*+<1/3>b*)*')
r.derived_term()

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:

c = vcsn.context('lat<lan, lan>, q')
c

$(\{\ldots\})^? \times (\{\ldots\})^?\to\mathbb{Q}$

e = c.expression('(a{+}|x + b{+}|y)*')
e

$\left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}$

e.derived_term('expansion')

e.derived_term('derivation')

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.

r = qexp('[ab]{2}')
r.derived_term()

r.derived_term(breaking=True)

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

r = qexp('a*+b*'); r

${a}^{*} + {b}^{*}$

a = r.derived_term(lazy=True)
a

print(a('')); a

2

print(a('a')); a

1

print(a('b')); a

1

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.

r = qexp('a*+(<2>a)*'); r

${a}^{*} + \left( \left\langle 2 \right\rangle \,a\right)^{*}$

a = r.derived_term(deterministic=True, lazy=True)
a

print(a('')); a

2

print(a('a')); a

3

print(a('aaa')); a

9

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.

r = r.complement()
r

$\left({a}^{*} + \left( \left\langle 2 \right\rangle \,a\right)^{*}\right)^{c}$

a = r.derived_term(lazy=True)
a

print(a('aa')); a

0

print(a('b')); a

1